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-2019 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 1.9.6
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 Create a new entry in the Neighbor cache
49  * @param[in] interface Underlying network interface
50  * @return Pointer to the newly created entry
51  **/
52 
54 {
55  uint_t i;
57  NdpNeighborCacheEntry *entry;
58  NdpNeighborCacheEntry *oldestEntry;
59 
60  //Get current time
62 
63  //Keep track of the oldest entry
64  oldestEntry = &interface->ndpContext.neighborCache[0];
65 
66  //Loop through Neighbor cache entries
67  for(i = 0; i < NDP_NEIGHBOR_CACHE_SIZE; i++)
68  {
69  //Point to the current entry
70  entry = &interface->ndpContext.neighborCache[i];
71 
72  //Check whether the entry is currently in used or not
73  if(entry->state == NDP_STATE_NONE)
74  {
75  //Erase contents
76  memset(entry, 0, sizeof(NdpNeighborCacheEntry));
77  //Return a pointer to the Neighbor cache entry
78  return entry;
79  }
80 
81  //Keep track of the oldest entry in the table
82  if((time - entry->timestamp) > (time - oldestEntry->timestamp))
83  {
84  oldestEntry = entry;
85  }
86  }
87 
88  //Drop any pending packets
89  ndpFlushQueuedPackets(interface, oldestEntry);
90  //The oldest entry is removed whenever the table runs out of space
91  memset(oldestEntry, 0, sizeof(NdpNeighborCacheEntry));
92 
93  //Return a pointer to the Neighbor cache entry
94  return oldestEntry;
95 }
96 
97 
98 /**
99  * @brief Search the Neighbor cache for a given IPv6 address
100  * @param[in] interface Underlying network interface
101  * @param[in] ipAddr IPv6 address
102  * @return A pointer to the matching entry is returned. NULL is returned if
103  * the specified IPv6 address could not be found in the Neighbor cache
104  **/
105 
107 {
108  uint_t i;
109  NdpNeighborCacheEntry *entry;
110 
111  //Loop through Neighbor cache entries
112  for(i = 0; i < NDP_NEIGHBOR_CACHE_SIZE; i++)
113  {
114  //Point to the current entry
115  entry = &interface->ndpContext.neighborCache[i];
116 
117  //Check whether the entry is currently in used
118  if(entry->state != NDP_STATE_NONE)
119  {
120  //Current entry matches the specified address?
121  if(ipv6CompAddr(&entry->ipAddr, ipAddr))
122  return entry;
123  }
124  }
125 
126  //No matching entry in Neighbor cache...
127  return NULL;
128 }
129 
130 
131 /**
132  * @brief Periodically update Neighbor cache
133  * @param[in] interface Underlying network interface
134  **/
135 
137 {
138  uint_t i;
139  systime_t time;
140  NdpNeighborCacheEntry *entry;
141 
142  //Get current time
143  time = osGetSystemTime();
144 
145  //Go through Neighbor cache
146  for(i = 0; i < NDP_NEIGHBOR_CACHE_SIZE; i++)
147  {
148  //Point to the current entry
149  entry = &interface->ndpContext.neighborCache[i];
150 
151  //INCOMPLETE state?
152  if(entry->state == NDP_STATE_INCOMPLETE)
153  {
154  //The Neighbor Solicitation timed out?
155  if(timeCompare(time, entry->timestamp + entry->timeout) >= 0)
156  {
157  //Increment retransmission counter
158  entry->retransmitCount++;
159 
160  //Check whether the maximum number of retransmissions has been exceeded
162  {
163  //Retransmit the multicast Neighbor Solicitation message
164  ndpSendNeighborSol(interface, &entry->ipAddr, TRUE);
165 
166  //Save the time at which the message was sent
167  entry->timestamp = time;
168  //Set timeout value
169  entry->timeout = interface->ndpContext.retransTimer;
170  }
171  else
172  {
173  //Drop packets that are waiting for address resolution
174  ndpFlushQueuedPackets(interface, entry);
175  //The entry should be deleted since address resolution has failed
176  entry->state = NDP_STATE_NONE;
177  }
178  }
179  }
180  //REACHABLE state?
181  else if(entry->state == NDP_STATE_REACHABLE)
182  {
183  //Periodically time out Neighbor cache entries
184  if(timeCompare(time, entry->timestamp + entry->timeout) >= 0)
185  {
186  //Save current time
187  entry->timestamp = osGetSystemTime();
188  //Enter STALE state
189  entry->state = NDP_STATE_STALE;
190  }
191  }
192  //STALE state?
193  else if(entry->state == NDP_STATE_STALE)
194  {
195  //The neighbor is no longer known to be reachable but until traffic
196  //is sent to the neighbor, no attempt should be made to verify its
197  //reachability
198  }
199  //DELAY state?
200  else if(entry->state == NDP_STATE_DELAY)
201  {
202  //Wait for the specified delay before sending the first probe
203  if(timeCompare(time, entry->timestamp + entry->timeout) >= 0)
204  {
206 
207  //Save the time at which the message was sent
208  entry->timestamp = time;
209  //Set timeout value
210  entry->timeout = interface->ndpContext.retransTimer;
211  //Switch to the PROBE state
212  entry->state = NDP_STATE_PROBE;
213 
214  //Target address
215  ipAddr = entry->ipAddr;
216 
217  //Send a unicast Neighbor Solicitation message
218  ndpSendNeighborSol(interface, &ipAddr, FALSE);
219  }
220  }
221  //PROBE state?
222  else if(entry->state == NDP_STATE_PROBE)
223  {
224  //The request timed out?
225  if(timeCompare(time, entry->timestamp + entry->timeout) >= 0)
226  {
227  //Increment retransmission counter
228  entry->retransmitCount++;
229 
230  //Check whether the maximum number of retransmissions has been exceeded
232  {
234 
235  //Save the time at which the packet was sent
236  entry->timestamp = time;
237  //Set timeout value
238  entry->timeout = interface->ndpContext.retransTimer;
239 
240  //Target address
241  ipAddr = entry->ipAddr;
242 
243  //Send a unicast Neighbor Solicitation message
244  ndpSendNeighborSol(interface, &ipAddr, FALSE);
245  }
246  else
247  {
248  //The entry should be deleted since the host is not reachable anymore
249  entry->state = NDP_STATE_NONE;
250 
251  //If at some point communication ceases to proceed, as determined
252  //by the Neighbor Unreachability Detection algorithm, next-hop
253  //determination may need to be performed again...
254  ndpUpdateNextHop(interface, &entry->ipAddr);
255  }
256  }
257  }
258  }
259 }
260 
261 
262 /**
263  * @brief Flush Neighbor cache
264  * @param[in] interface Underlying network interface
265  **/
266 
268 {
269  uint_t i;
270  NdpNeighborCacheEntry *entry;
271 
272  //Loop through Neighbor cache entries
273  for(i = 0; i < NDP_NEIGHBOR_CACHE_SIZE; i++)
274  {
275  //Point to the current entry
276  entry = &interface->ndpContext.neighborCache[i];
277 
278  //Drop packets that are waiting for address resolution
279  ndpFlushQueuedPackets(interface, entry);
280  //Release Neighbor cache entry
281  entry->state = NDP_STATE_NONE;
282  }
283 }
284 
285 
286 /**
287  * @brief Send packets that are waiting for address resolution
288  * @param[in] interface Underlying network interface
289  * @param[in] entry Pointer to a Neighbor cache entry
290  * @return The number of packets that have been sent
291  **/
292 
294 {
295  uint_t i;
296  NdpQueueItem *item;
297 #if (ETH_SUPPORT == ENABLED)
298  NetInterface *physicalInterface;
299 
300  //Point to the physical interface
301  physicalInterface = nicGetPhysicalInterface(interface);
302 #endif
303 
304  //Reset packet counter
305  i = 0;
306 
307  //Check current state
308  if(entry->state == NDP_STATE_INCOMPLETE)
309  {
310  //Loop through the queued packets
311  for(i = 0; i < entry->queueSize; i++)
312  {
313  //Point to the current queue item
314  item = &entry->queue[i];
315 
316 #if (ETH_SUPPORT == ENABLED)
317  //Ethernet interface?
318  if(physicalInterface->nicDriver != NULL &&
319  physicalInterface->nicDriver->type == NIC_TYPE_ETHERNET)
320  {
321  size_t length;
322 
323  //Retrieve the length of the IPv6 packet
324  length = netBufferGetLength(item->buffer) - item->offset;
325  //Update IP statistics
326  ipv6UpdateOutStats(interface, &entry->ipAddr, length);
327 
328  //Send the IPv6 packet
329  ethSendFrame(interface, &entry->macAddr,
330  item->buffer, item->offset, ETH_TYPE_IPV6);
331  }
332 #endif
333  //Release memory buffer
334  netBufferFree(item->buffer);
335  }
336  }
337 
338  //The queue is now empty
339  entry->queueSize = 0;
340 
341  //Return the number of packets that have been sent
342  return i;
343 }
344 
345 
346 /**
347  * @brief Flush packet queue
348  * @param[in] interface Underlying network interface
349  * @param[in] entry Pointer to a Neighbor cache entry
350  **/
351 
353 {
354  uint_t i;
355  NdpQueueItem *item;
356 
357  //Check current state
358  if(entry->state == NDP_STATE_INCOMPLETE)
359  {
360  //Loop through the queued packets
361  for(i = 0; i < entry->queueSize; i++)
362  {
363  //Point to the current queue item
364  item = &entry->queue[i];
365 
366  //Check whether the address resolution has failed
368  {
369  //Check whether the packet has been forwarded
370  if(item->srcInterface != NULL)
371  {
372  //A Destination Unreachable message should be generated by a
373  //router in response to a packet that cannot be delivered
375  ICMPV6_CODE_ADDR_UNREACHABLE, 0, item->buffer, item->offset);
376  }
377  }
378 
379  //Release memory buffer
380  netBufferFree(item->buffer);
381  }
382  }
383 
384  //The queue is now empty
385  entry->queueSize = 0;
386 }
387 
388 
389 /**
390  * @brief Create a new entry in the Destination Cache
391  * @param[in] interface Underlying network interface
392  * @return Pointer to the newly created entry
393  **/
394 
396 {
397  uint_t i;
398  systime_t time;
399  NdpDestCacheEntry *entry;
400  NdpDestCacheEntry *oldestEntry;
401 
402  //Get current time
403  time = osGetSystemTime();
404 
405  //Keep track of the oldest entry
406  oldestEntry = &interface->ndpContext.destCache[0];
407 
408  //Loop through Destination cache entries
409  for(i = 0; i < NDP_DEST_CACHE_SIZE; i++)
410  {
411  //Point to the current entry
412  entry = &interface->ndpContext.destCache[i];
413 
414  //Check whether the entry is currently in used or not
416  {
417  //Erase contents
418  memset(entry, 0, sizeof(NdpDestCacheEntry));
419  //Return a pointer to the Destination cache entry
420  return entry;
421  }
422 
423  //Keep track of the oldest entry in the table
424  if((time - entry->timestamp) > (time - oldestEntry->timestamp))
425  {
426  oldestEntry = entry;
427  }
428  }
429 
430  //The oldest entry is removed whenever the table runs out of space
431  memset(oldestEntry, 0, sizeof(NdpDestCacheEntry));
432 
433  //Return a pointer to the Destination cache entry
434  return oldestEntry;
435 }
436 
437 
438 /**
439  * @brief Search the Destination Cache for a given destination address
440  * @param[in] interface Underlying network interface
441  * @param[in] destAddr Destination IPv6 address
442  * @return A pointer to the matching entry is returned. NULL is returned if
443  * the specified address could not be found in the Destination cache
444  **/
445 
447 {
448  uint_t i;
449  NdpDestCacheEntry *entry;
450 
451  //Loop through Destination Cache entries
452  for(i = 0; i < NDP_DEST_CACHE_SIZE; i++)
453  {
454  //Point to the current entry
455  entry = &interface->ndpContext.destCache[i];
456 
457  //Current entry matches the specified destination address?
458  if(ipv6CompAddr(&entry->destAddr, destAddr))
459  return entry;
460  }
461 
462  //No matching entry in Destination Cache...
463  return NULL;
464 }
465 
466 
467 /**
468  * @brief Flush Destination Cache
469  * @param[in] interface Underlying network interface
470  **/
471 
473 {
474  //Clear the Destination Cache
475  memset(interface->ndpContext.destCache, 0,
476  sizeof(interface->ndpContext.destCache));
477 }
478 
479 #endif
NdpNeighborCacheEntry * ndpFindNeighborCacheEntry(NetInterface *interface, const Ipv6Addr *ipAddr)
Search the Neighbor cache for a given IPv6 address.
Definition: ndp_cache.c:106
@ ICMPV6_TYPE_DEST_UNREACHABLE
Definition: icmpv6.h:53
uint8_t length
Definition: dtls_misc.h:149
#define NDP_MAX_UNICAST_SOLICIT
Definition: ndp.h:151
@ NDP_STATE_STALE
Definition: ndp.h:252
Helper functions for NDP (Neighbor Discovery Protocol)
error_t ethSendFrame(NetInterface *interface, const MacAddr *destAddr, NetBuffer *buffer, size_t offset, uint16_t type)
Send an Ethernet frame.
Definition: ethernet.c:345
void ipv6UpdateOutStats(NetInterface *interface, const Ipv6Addr *destIpAddr, size_t length)
Update IPv6 output statistics.
Definition: ipv6_misc.c:1505
#define TRUE
Definition: os_port.h:50
NdpDestCacheEntry * ndpFindDestCacheEntry(NetInterface *interface, const Ipv6Addr *destAddr)
Search the Destination Cache for a given destination address.
Definition: ndp_cache.c:446
#define NDP_NEIGHBOR_CACHE_SIZE
Definition: ndp.h:53
void ndpFlushQueuedPackets(NetInterface *interface, NdpNeighborCacheEntry *entry)
Flush packet queue.
Definition: ndp_cache.c:352
uint_t queueSize
Number of queued packets.
Definition: ndp.h:554
Neighbor cache entry.
Definition: ndp.h:544
#define ipv6CompAddr(ipAddr1, ipAddr2)
Definition: ipv6.h:121
error_t ndpSendNeighborSol(NetInterface *interface, const Ipv6Addr *targetIpAddr, bool_t multicast)
Send a Neighbor Solicitation message.
Definition: ndp.c:1473
@ NDP_STATE_NONE
Definition: ndp.h:249
Ipv6Addr destAddr
Destination IPv6 address.
Definition: ndp.h:564
#define timeCompare(t1, t2)
Definition: os_port.h:42
size_t offset
Offset to the first byte of the packet.
Definition: ndp.h:536
MacAddr destAddr
Definition: ethernet.h:192
systime_t timestamp
Timestamp to manage entry lifetime.
Definition: ndp.h:550
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:462
#define FALSE
Definition: os_port.h:46
ICMPv6 (Internet Control Message Protocol Version 6)
NetInterface * nicGetPhysicalInterface(NetInterface *interface)
Retrieve physical interface.
Definition: nic.c:84
MacAddr macAddr
Link layer address associated with the IPv6 address.
Definition: ndp.h:548
@ ICMPV6_CODE_ADDR_UNREACHABLE
Definition: icmpv6.h:80
systime_t timestamp
Timestamp to manage entry lifetime.
Definition: ndp.h:567
NdpNeighborCacheEntry * ndpCreateNeighborCacheEntry(NetInterface *interface)
Create a new entry in the Neighbor cache.
Definition: ndp_cache.c:53
NdpDestCacheEntry * ndpCreateDestCacheEntry(NetInterface *interface)
Create a new entry in the Destination Cache.
Definition: ndp_cache.c:395
#define NetInterface
Definition: net.h:36
void netBufferFree(NetBuffer *buffer)
Dispose a multi-part buffer.
Definition: net_mem.c:282
uint_t ndpSendQueuedPackets(NetInterface *interface, NdpNeighborCacheEntry *entry)
Send packets that are waiting for address resolution.
Definition: ndp_cache.c:293
@ NDP_STATE_DELAY
Definition: ndp.h:253
Helper functions for IPv6.
void ndpUpdateNextHop(NetInterface *interface, const Ipv6Addr *unreachableNextHop)
Update next-hop field of Destination Cache entries.
Definition: ndp_misc.c:558
const Ipv6Addr IPV6_UNSPECIFIED_ADDR
Definition: ipv6.c:67
__start_packed struct @179 Ipv6Addr
IPv6 network address.
size_t netBufferGetLength(const NetBuffer *buffer)
Get the actual length of a multi-part buffer.
Definition: net_mem.c:297
@ NDP_STATE_INCOMPLETE
Definition: ndp.h:250
#define NDP_MAX_MULTICAST_SOLICIT
Definition: ndp.h:144
Neighbor and destination cache management.
#define NDP_DEST_CACHE_SIZE
Definition: ndp.h:60
@ NDP_STATE_REACHABLE
Definition: ndp.h:251
NDP (Neighbor Discovery Protocol)
NdpQueueItem queue[NDP_MAX_PENDING_PACKETS]
Packets waiting for address resolution to complete.
Definition: ndp.h:553
void ndpFlushNeighborCache(NetInterface *interface)
Flush Neighbor cache.
Definition: ndp_cache.c:267
void ndpUpdateNeighborCache(NetInterface *interface)
Periodically update Neighbor cache.
Definition: ndp_cache.c:136
NDP queue item.
Definition: ndp.h:532
void ndpFlushDestCache(NetInterface *interface)
Flush Destination Cache.
Definition: ndp_cache.c:472
uint32_t time
Ipv6Addr ipAddr
Unicast IPv6 address.
Definition: ndp.h:547
NetInterface * srcInterface
Definition: ndp.h:534
@ ETH_TYPE_IPV6
Definition: ethernet.h:145
NdpState state
Reachability state.
Definition: ndp.h:546
Destination cache entry.
Definition: ndp.h:562
uint_t retransmitCount
Retransmission counter.
Definition: ndp.h:552
NetBuffer * buffer
Packet waiting for address resolution.
Definition: ndp.h:535
unsigned int uint_t
Definition: compiler_port.h:45
TCP/IP stack core.
@ NDP_STATE_PROBE
Definition: ndp.h:254
uint32_t systime_t
Definition: compiler_port.h:46
uint8_t ipAddr[4]
Definition: mib_common.h:187
systime_t timeout
Timeout value.
Definition: ndp.h:551
Debugging facilities.
@ NIC_TYPE_ETHERNET
Ethernet interface.
Definition: nic.h:79
systime_t osGetSystemTime(void)
Retrieve system time.