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