ndp_cache.c

00001 /**
00002  * @file ndp_cache.c
00003  * @brief Neighbor and destination cache management
00004  *
00005  * @section License
00006  *
00007  * Copyright (C) 2010-2017 Oryx Embedded SARL. All rights reserved.
00008  *
00009  * This file is part of CycloneTCP Open.
00010  *
00011  * This program is free software; you can redistribute it and/or
00012  * modify it under the terms of the GNU General Public License
00013  * as published by the Free Software Foundation; either version 2
00014  * of the License, or (at your option) any later version.
00015  *
00016  * This program is distributed in the hope that it will be useful,
00017  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00018  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00019  * GNU General Public License for more details.
00020  *
00021  * You should have received a copy of the GNU General Public License
00022  * along with this program; if not, write to the Free Software Foundation,
00023  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
00024  *
00025  * @author Oryx Embedded SARL (www.oryx-embedded.com)
00026  * @version 1.7.6
00027  **/
00028 
00029 //Switch to the appropriate trace level
00030 #define TRACE_LEVEL NDP_TRACE_LEVEL
00031 
00032 //Dependencies
00033 #include "core/net.h"
00034 #include "ipv6/icmpv6.h"
00035 #include "ipv6/ndp.h"
00036 #include "ipv6/ndp_cache.h"
00037 #include "ipv6/ndp_misc.h"
00038 #include "debug.h"
00039 
00040 //Check TCP/IP stack configuration
00041 #if (IPV6_SUPPORT == ENABLED && NDP_SUPPORT == ENABLED)
00042 
00043 
00044 /**
00045  * @brief Create a new entry in the Neighbor cache
00046  * @param[in] interface Underlying network interface
00047  * @return Pointer to the newly created entry
00048  **/
00049 
00050 NdpNeighborCacheEntry *ndpCreateNeighborCacheEntry(NetInterface *interface)
00051 {
00052    uint_t i;
00053    NdpNeighborCacheEntry *entry;
00054    NdpNeighborCacheEntry *oldestEntry;
00055 
00056    //Keep track of the oldest entry
00057    oldestEntry = &interface->ndpContext.neighborCache[0];
00058 
00059    //Loop through Neighbor cache entries
00060    for(i = 0; i < NDP_NEIGHBOR_CACHE_SIZE; i++)
00061    {
00062       //Point to the current entry
00063       entry = &interface->ndpContext.neighborCache[i];
00064 
00065       //Check whether the entry is currently in used or not
00066       if(entry->state == NDP_STATE_NONE)
00067       {
00068          //Erase contents
00069          memset(entry, 0, sizeof(NdpNeighborCacheEntry));
00070          //Return a pointer to the Neighbor cache entry
00071          return entry;
00072       }
00073 
00074       //Keep track of the oldest entry in the table
00075       if(timeCompare(entry->timestamp, oldestEntry->timestamp) < 0)
00076          oldestEntry = entry;
00077    }
00078 
00079    //Drop any pending packets
00080    ndpFlushQueuedPackets(interface, oldestEntry);
00081    //The oldest entry is removed whenever the table runs out of space
00082    memset(oldestEntry, 0, sizeof(NdpNeighborCacheEntry));
00083 
00084    //Return a pointer to the Neighbor cache entry
00085    return oldestEntry;
00086 }
00087 
00088 
00089 /**
00090  * @brief Search the Neighbor cache for a given IPv6 address
00091  * @param[in] interface Underlying network interface
00092  * @param[in] ipAddr IPv6 address
00093  * @return A pointer to the matching entry is returned. NULL is returned if
00094  *   the specified IPv6 address could not be found in the Neighbor cache
00095  **/
00096 
00097 NdpNeighborCacheEntry *ndpFindNeighborCacheEntry(NetInterface *interface, const Ipv6Addr *ipAddr)
00098 {
00099    uint_t i;
00100    NdpNeighborCacheEntry *entry;
00101 
00102    //Loop through Neighbor cache entries
00103    for(i = 0; i < NDP_NEIGHBOR_CACHE_SIZE; i++)
00104    {
00105       //Point to the current entry
00106       entry = &interface->ndpContext.neighborCache[i];
00107 
00108       //Check whether the entry is currently in used
00109       if(entry->state != NDP_STATE_NONE)
00110       {
00111          //Current entry matches the specified address?
00112          if(ipv6CompAddr(&entry->ipAddr, ipAddr))
00113             return entry;
00114       }
00115    }
00116 
00117    //No matching entry in Neighbor cache...
00118    return NULL;
00119 }
00120 
00121 
00122 /**
00123  * @brief Periodically update Neighbor cache
00124  * @param[in] interface Underlying network interface
00125  **/
00126 
00127 void ndpUpdateNeighborCache(NetInterface *interface)
00128 {
00129    uint_t i;
00130    systime_t time;
00131    NdpNeighborCacheEntry *entry;
00132 
00133    //Get current time
00134    time = osGetSystemTime();
00135 
00136    //Go through Neighbor cache
00137    for(i = 0; i < NDP_NEIGHBOR_CACHE_SIZE; i++)
00138    {
00139       //Point to the current entry
00140       entry = &interface->ndpContext.neighborCache[i];
00141 
00142       //INCOMPLETE state?
00143       if(entry->state == NDP_STATE_INCOMPLETE)
00144       {
00145          //The Neighbor Solicitation timed out?
00146          if(timeCompare(time, entry->timestamp + entry->timeout) >= 0)
00147          {
00148             //Increment retransmission counter
00149             entry->retransmitCount++;
00150 
00151             //Check whether the maximum number of retransmissions has been exceeded
00152             if(entry->retransmitCount < NDP_MAX_MULTICAST_SOLICIT)
00153             {
00154                //Retransmit the multicast Neighbor Solicitation message
00155                ndpSendNeighborSol(interface, &entry->ipAddr, TRUE);
00156 
00157                //Save the time at which the message was sent
00158                entry->timestamp = time;
00159                //Set timeout value
00160                entry->timeout = interface->ndpContext.retransTimer;
00161             }
00162             else
00163             {
00164                //Drop packets that are waiting for address resolution
00165                ndpFlushQueuedPackets(interface, entry);
00166                //The entry should be deleted since address resolution has failed
00167                entry->state = NDP_STATE_NONE;
00168             }
00169          }
00170       }
00171       //REACHABLE state?
00172       else if(entry->state == NDP_STATE_REACHABLE)
00173       {
00174          //Periodically time out Neighbor cache entries
00175          if(timeCompare(time, entry->timestamp + entry->timeout) >= 0)
00176          {
00177             //Save current time
00178             entry->timestamp = osGetSystemTime();
00179             //Enter STALE state
00180             entry->state = NDP_STATE_STALE;
00181          }
00182       }
00183       //STALE state?
00184       else if(entry->state == NDP_STATE_STALE)
00185       {
00186          //The neighbor is no longer known to be reachable but until traffic
00187          //is sent to the neighbor, no attempt should be made to verify its
00188          //reachability
00189       }
00190       //DELAY state?
00191       else if(entry->state == NDP_STATE_DELAY)
00192       {
00193          //Wait for the specified delay before sending the first probe
00194          if(timeCompare(time, entry->timestamp + entry->timeout) >= 0)
00195          {
00196             Ipv6Addr ipAddr;
00197 
00198             //Save the time at which the message was sent
00199             entry->timestamp = time;
00200             //Set timeout value
00201             entry->timeout = interface->ndpContext.retransTimer;
00202             //Switch to the PROBE state
00203             entry->state = NDP_STATE_PROBE;
00204 
00205             //Target address
00206             ipAddr = entry->ipAddr;
00207 
00208             //Send a unicast Neighbor Solicitation message
00209             ndpSendNeighborSol(interface, &ipAddr, FALSE);
00210          }
00211       }
00212       //PROBE state?
00213       else if(entry->state == NDP_STATE_PROBE)
00214       {
00215          //The request timed out?
00216          if(timeCompare(time, entry->timestamp + entry->timeout) >= 0)
00217          {
00218             //Increment retransmission counter
00219             entry->retransmitCount++;
00220 
00221             //Check whether the maximum number of retransmissions has been exceeded
00222             if(entry->retransmitCount < NDP_MAX_UNICAST_SOLICIT)
00223             {
00224                Ipv6Addr ipAddr;
00225 
00226                //Save the time at which the packet was sent
00227                entry->timestamp = time;
00228                //Set timeout value
00229                entry->timeout = interface->ndpContext.retransTimer;
00230 
00231                //Target address
00232                ipAddr = entry->ipAddr;
00233 
00234                //Send a unicast Neighbor Solicitation message
00235                ndpSendNeighborSol(interface, &ipAddr, FALSE);
00236             }
00237             else
00238             {
00239                //The entry should be deleted since the host is not reachable anymore
00240                entry->state = NDP_STATE_NONE;
00241 
00242                //If at some point communication ceases to proceed, as determined
00243                //by the Neighbor Unreachability Detection algorithm, next-hop
00244                //determination may need to be performed again...
00245                ndpUpdateNextHop(interface, &entry->ipAddr);
00246             }
00247          }
00248       }
00249    }
00250 }
00251 
00252 
00253 /**
00254  * @brief Flush Neighbor cache
00255  * @param[in] interface Underlying network interface
00256  **/
00257 
00258 void ndpFlushNeighborCache(NetInterface *interface)
00259 {
00260    uint_t i;
00261    NdpNeighborCacheEntry *entry;
00262 
00263    //Loop through Neighbor cache entries
00264    for(i = 0; i < NDP_NEIGHBOR_CACHE_SIZE; i++)
00265    {
00266       //Point to the current entry
00267       entry = &interface->ndpContext.neighborCache[i];
00268 
00269       //Drop packets that are waiting for address resolution
00270       ndpFlushQueuedPackets(interface, entry);
00271       //Release Neighbor cache entry
00272       entry->state = NDP_STATE_NONE;
00273    }
00274 }
00275 
00276 
00277 /**
00278  * @brief Send packets that are waiting for address resolution
00279  * @param[in] interface Underlying network interface
00280  * @param[in] entry Pointer to a Neighbor cache entry
00281  * @return The number of packets that have been sent
00282  **/
00283 
00284 uint_t ndpSendQueuedPackets(NetInterface *interface, NdpNeighborCacheEntry *entry)
00285 {
00286    uint_t i;
00287    NdpQueueItem *item;
00288 
00289    //Reset packet counter
00290    i = 0;
00291 
00292    //Check current state
00293    if(entry->state == NDP_STATE_INCOMPLETE)
00294    {
00295       //Loop through the queued packets
00296       for(i = 0; i < entry->queueSize; i++)
00297       {
00298          //Point to the current queue item
00299          item = &entry->queue[i];
00300 
00301 #if (ETH_SUPPORT == ENABLED)
00302          //Ethernet interface?
00303          if(interface->nicDriver->type == NIC_TYPE_ETHERNET)
00304          {
00305             //Send the IPv6 packet
00306             ethSendFrame(interface, &entry->macAddr,
00307                item->buffer, item->offset, ETH_TYPE_IPV6);
00308          }
00309 #endif
00310          //Release memory buffer
00311          netBufferFree(item->buffer);
00312       }
00313    }
00314 
00315    //The queue is now empty
00316    entry->queueSize = 0;
00317 
00318    //Return the number of packets that have been sent
00319    return i;
00320 }
00321 
00322 
00323 /**
00324  * @brief Flush packet queue
00325  * @param[in] interface Underlying network interface
00326  * @param[in] entry Pointer to a Neighbor cache entry
00327  **/
00328 
00329 void ndpFlushQueuedPackets(NetInterface *interface, NdpNeighborCacheEntry *entry)
00330 {
00331    uint_t i;
00332    NdpQueueItem *item;
00333 
00334    //Check current state
00335    if(entry->state == NDP_STATE_INCOMPLETE)
00336    {
00337       //Loop through the queued packets
00338       for(i = 0; i < entry->queueSize; i++)
00339       {
00340          //Point to the current queue item
00341          item = &entry->queue[i];
00342 
00343          //Check whether the address resolution has failed
00344          if(entry->retransmitCount >= NDP_MAX_MULTICAST_SOLICIT)
00345          {
00346             //Check whether the packet has been forwarded
00347             if(item->srcInterface != NULL)
00348             {
00349                //A Destination Unreachable message should be generated by a
00350                //router in response to a packet that cannot be delivered
00351                icmpv6SendErrorMessage(item->srcInterface, ICMPV6_TYPE_DEST_UNREACHABLE,
00352                   ICMPV6_CODE_ADDR_UNREACHABLE, 0, item->buffer, item->offset);
00353             }
00354          }
00355 
00356          //Release memory buffer
00357          netBufferFree(item->buffer);
00358       }
00359    }
00360 
00361    //The queue is now empty
00362    entry->queueSize = 0;
00363 }
00364 
00365 
00366 /**
00367  * @brief Create a new entry in the Destination Cache
00368  * @param[in] interface Underlying network interface
00369  * @return Pointer to the newly created entry
00370  **/
00371 
00372 NdpDestCacheEntry *ndpCreateDestCacheEntry(NetInterface *interface)
00373 {
00374    uint_t i;
00375    NdpDestCacheEntry *entry;
00376    NdpDestCacheEntry *oldestEntry;
00377 
00378    //Keep track of the oldest entry
00379    oldestEntry = &interface->ndpContext.destCache[0];
00380 
00381    //Loop through Destination cache entries
00382    for(i = 0; i < NDP_DEST_CACHE_SIZE; i++)
00383    {
00384       //Point to the current entry
00385       entry = &interface->ndpContext.destCache[i];
00386 
00387       //Check whether the entry is currently in used or not
00388       if(ipv6CompAddr(&entry->destAddr, &IPV6_UNSPECIFIED_ADDR))
00389       {
00390          //Erase contents
00391          memset(entry, 0, sizeof(NdpDestCacheEntry));
00392          //Return a pointer to the Destination cache entry
00393          return entry;
00394       }
00395 
00396       //Keep track of the oldest entry in the table
00397       if(timeCompare(entry->timestamp, oldestEntry->timestamp) < 0)
00398          oldestEntry = entry;
00399    }
00400 
00401    //The oldest entry is removed whenever the table runs out of space
00402    memset(oldestEntry, 0, sizeof(NdpDestCacheEntry));
00403 
00404    //Return a pointer to the Destination cache entry
00405    return oldestEntry;
00406 }
00407 
00408 
00409 /**
00410  * @brief Search the Destination Cache for a given destination address
00411  * @param[in] interface Underlying network interface
00412  * @param[in] destAddr Destination IPv6 address
00413  * @return A pointer to the matching entry is returned. NULL is returned if
00414  *   the specified address could not be found in the Destination cache
00415  **/
00416 
00417 NdpDestCacheEntry *ndpFindDestCacheEntry(NetInterface *interface, const Ipv6Addr *destAddr)
00418 {
00419    uint_t i;
00420    NdpDestCacheEntry *entry;
00421 
00422    //Loop through Destination Cache entries
00423    for(i = 0; i < NDP_DEST_CACHE_SIZE; i++)
00424    {
00425       //Point to the current entry
00426       entry = &interface->ndpContext.destCache[i];
00427 
00428       //Current entry matches the specified destination address?
00429       if(ipv6CompAddr(&entry->destAddr, destAddr))
00430          return entry;
00431    }
00432 
00433    //No matching entry in Destination Cache...
00434    return NULL;
00435 }
00436 
00437 
00438 /**
00439  * @brief Flush Destination Cache
00440  * @param[in] interface Underlying network interface
00441  **/
00442 
00443 void ndpFlushDestCache(NetInterface *interface)
00444 {
00445    //Clear the Destination Cache
00446    memset(interface->ndpContext.destCache, 0,
00447       sizeof(interface->ndpContext.destCache));
00448 }
00449 
00450 #endif
00451