KernelLand/Modules/IPStack/hwaddr_cache.c

   1 /*
   2  * Acess2 IP Stack
   3  *
   4  * hwaddr_resolution.c
   5  * - Resolution/caching of hardware addresses
   6  */
   7 #define DEBUG   1
   8 #include "ipstack.h"
   9 #include "icmp.h"
  10 #include "include/adapters_int.h"
  11 #include "hwaddr_cache.h"
  12 #include <timers.h>
  13 #include <semaphore.h>
  14 #include <limits.h>     // *INT_MAX
  15
  16 typedef struct sHWAdddrCache    tHWAddrCache;
  17 typedef struct sHWAdddrCachedAddr       tHWAddrCachedAddr;
  18
  19 struct sHWAdddrCache {
  20         const tInterface        *Interface;
  21         tMutex  Lock;
  22         const int       MaxSize;
  23          int    nAddrs;
  24         tHWAddrCachedAddr       *First;
  25 };
  26
  27 struct sHWAdddrCachedAddr {
  28         tHWAddrCachedAddr       *Next;
  29         unsigned int    WaitingCount;   // While >0, cache will not be reused
  30         tSemaphore      WaitingSem;
  31         void    *L3Addr;
  32         tMacAddr        *HWAddr;
  33 };
  34
  35 #define PRImacaddr      "%02x:%02x:%02x:%02x:%02x:%02x"
  36 #define FMTmacaddr(a)   (a).B[0],(a).B[1],(a).B[2],(a).B[3],(a).B[4],(a).B[5]
  37
  38 // Cache is sorted by usage (most recently used at top)
  39
  40 // === CODE ===
  41 tHWAddrCache *HWCache_int_GetCache(tAdapter *Adapter, int AddrType)
  42 {
  43         static tHWAddrCache     cache_v6 = {.MaxSize=64};
  44         static tHWAddrCache     cache_v4 = {.MaxSize=64};
  45         switch(AddrType)
  46         {
  47         case 4: return &cache_v4;
  48         case 6: return &cache_v6;
  49         default:
  50                 return NULL;
  51         }
  52 }
  53
  54 bool memiszero(const void *mem, size_t length)
  55 {
  56         const Uint8     *mem8 = mem;
  57         while( length -- )
  58         {
  59                 if(*mem8 != 0)  return false;
  60                 mem8 ++;
  61         }
  62         return true;
  63 }
  64
  65 tMacAddr HWCache_Resolve(tInterface *Interface, const void *DestAddr)
  66 {
  67         const size_t    addrsize = IPStack_GetAddressSize(Interface->Type);
  68         tHWAddrCache    *cache = HWCache_int_GetCache(Interface->Adapter, Interface->Type);
  69
  70         LOG("DestAddr=%s", IPStack_PrintAddress(Interface->Type, DestAddr));
  71
  72         // Detect sending packets outside of the local network
  73         if( IPStack_CompareAddress(Interface->Type, DestAddr, Interface->Address, Interface->SubnetBits) == 0 )
  74         {
  75                 // Off-net, use a route
  76                 tRoute  *route = IPStack_FindRoute(Interface->Type, Interface, DestAddr);
  77                 // If a route exists and the gateway isn't empty, use the gateway
  78                 if( route )
  79                 {
  80                         if( !memiszero(route->NextHop, addrsize) )
  81                         {
  82                                 // Update DestAddr to gateway address
  83                                 DestAddr = route->NextHop;
  84                                 LOG("Via gateway");
  85                         }
  86                         else
  87                         {
  88                                 // Zero gateway means force direct
  89                                 LOG("Force direct");
  90                         }
  91                 }
  92                 else
  93                 {
  94                         // No route to host
  95                         LOG("No route to host");
  96                         return cMAC_ZERO;
  97                 }
  98         }
  99         // Local broadcast
 100         else if( IPStack_AddressIsBroadcast(Interface->Type, DestAddr, Interface->SubnetBits) )
 101         {
 102                 // Broadcast, send to bcast mac
 103                 LOG("Broadcast");
 104                 return cMAC_BROADCAST;
 105         }
 106         else
 107         {
 108                 // Fall through
 109         }
 110         LOG("DestAddr(2)=%s", IPStack_PrintAddress(Interface->Type, DestAddr));
 111
 112         Mutex_Acquire(&cache->Lock);
 113         // 1. Search cache for this address
 114         tHWAddrCachedAddr **pnp = &cache->First, *ca;
 115         tHWAddrCachedAddr *last = NULL;
 116         for( ca = cache->First; ca; ca = ca->Next )
 117         {
 118                 LOG("ca = %p (%s => "PRImacaddr")",
 119                         ca, IPStack_PrintAddress(Interface->Type, ca->L3Addr),
 120                         FMTmacaddr(*ca->HWAddr)
 121                         );
 122                 if( memcmp(ca->L3Addr, DestAddr, addrsize) == 0 )
 123                         break;
 124                 last = ca;
 125                 pnp = &ca->Next;
 126         }
 127         if( ca )
 128         {
 129                 // Move to front, return
 130                 if( cache->First != ca )
 131                 {
 132                         ASSERT(pnp != &cache->First);
 133                         *pnp = ca->Next;
 134
 135                         ca->Next = cache->First;
 136                         cache->First = ca;
 137                         LOG("%p(%s) bumped", ca, IPStack_PrintAddress(Interface->Type, ca->L3Addr));
 138                 }
 139
 140                 // If there's something waiting on this, odds are it's not populated
 141                 if( ca->WaitingCount > 0 )
 142                 {
 143                         ASSERT(ca->WaitingCount != UINT_MAX);
 144                         ca->WaitingCount ++;
 145                         Mutex_Release(&cache->Lock);
 146
 147                         // Wait until populated
 148                         LOG("Waiting on %p", ca);
 149                         Semaphore_Wait(&ca->WaitingSem, 1);
 150
 151                         Mutex_Acquire(&cache->Lock);
 152                         ASSERT(ca->WaitingCount > 0);
 153                         ca->WaitingCount --;
 154                 }
 155                 tMacAddr ret = *(tMacAddr*)ca->HWAddr;
 156                 Mutex_Release(&cache->Lock);
 157
 158                 LOG("Cached "PRImacaddr, FMTmacaddr(ret));
 159                 return ret;
 160         }
 161         // 3. If not found:
 162         if( cache->nAddrs >= cache->MaxSize )
 163         {
 164                 ASSERTC(cache->nAddrs, ==, cache->MaxSize);
 165                 ASSERT(last);
 166                 // TODO: Need to pick the oldest entry with WaitingThreads==0
 167                 ASSERT(ca->WaitingCount == 0);
 168                 // Reuse the oldest item
 169                 ca = last;
 170                 LOG("Reuse entry for %p(%s)", ca, IPStack_PrintAddress(Interface->Type, ca->L3Addr));
 171         }
 172         else
 173         {
 174                 cache->nAddrs ++;
 175                 ca = calloc( 1, sizeof(*ca) + addrsize + sizeof(tMacAddr) );
 176                 ca->L3Addr = ca+1;
 177                 ca->HWAddr = (void*)( (char*)ca->L3Addr + addrsize );
 178                 LOG("New entry %p", ca);
 179         }
 180         memcpy(ca->L3Addr, DestAddr, addrsize);
 181         memset(ca->HWAddr, 0, sizeof(tMacAddr));
 182
 183         // Shift to front of list
 184         if( cache->First != ca )
 185         {
 186                 *pnp = ca->Next;
 187                 ca->Next = cache->First;
 188                 cache->First = ca;
 189         }
 190
 191         // Mark cache entry as being waited upon
 192         ASSERT(ca->WaitingCount == 0);
 193         ca->WaitingCount = 1;
 194         // Then release cache lock (so inbound packets can manipulate it)
 195         Mutex_Release(&cache->Lock);
 196
 197         // Send a request for the address
 198         switch(Interface->Type)
 199         {
 200         case 4: ARP_Request4(Interface, *(tIPv4*)DestAddr);     break;
 201         //case 6:       ICMPv6_RequestND(Interface, DestAddr);  break;
 202         default:
 203                 ASSERTC(Interface->Type, ==, 4);
 204                 ASSERTC(Interface->Type, ==, 6);
 205                 break;
 206         }
 207
 208         // Wait for up to 3000ms for the entry to populate
 209         LOG("Waiting on new entry");
 210         Time_ScheduleEvent(3000);
 211         int rv = Semaphore_Wait(&ca->WaitingSem, 1);
 212
 213         // Lock, reduce waiting count, grab return, and release
 214         Mutex_Acquire(&cache->Lock);
 215         ASSERT(ca->WaitingCount > 0);
 216         ca->WaitingCount --;
 217         tMacAddr        ret = *(tMacAddr*)ca->HWAddr;
 218         Mutex_Release(&cache->Lock);
 219
 220         // NOTE: If entry wasn't populated, we'd return 0 anyway, this is
 221         //   just for logging purposes
 222         if( rv != 1 )
 223         {
 224                 // Interrupted, return zero MAC
 225                 LOG("Timeout/interrupt, return zero");
 226                 return cMAC_ZERO;
 227         }
 228
 229         // Release `ca` (on error, HWAddr will be nul)
 230         LOG("Requested "PRImacaddr, FMTmacaddr(ret));
 231         return ret;
 232 }
 233
 234 void HWCache_Set(tAdapter *Adapter, int AddrType, const void *L3Addr, const tMacAddr *HWAddr)
 235 {
 236         const size_t    addrsize = IPStack_GetAddressSize(AddrType);
 237         tHWAddrCache    *cache = HWCache_int_GetCache(Adapter, AddrType);
 238         LOG("Set %s = "PRImacaddr,
 239                 IPStack_PrintAddress(AddrType, L3Addr),
 240                 FMTmacaddr(*HWAddr)
 241                 );
 242         // 1. Locate an existing entry
 243         Mutex_Acquire(&cache->Lock);
 244         tHWAddrCachedAddr       *last_unused = NULL;
 245         tHWAddrCachedAddr       **pnp = &cache->First;
 246         for( tHWAddrCachedAddr *ca = cache->First; ca; ca = ca->Next )
 247         {
 248                 ASSERT(ca->Next != ca);
 249                 ASSERT(!ca->Next || ca->Next->Next != ca);
 250
 251                 LOG("ca = %p (%s => "PRImacaddr")",
 252                         ca, IPStack_PrintAddress(AddrType, ca->L3Addr), FMTmacaddr(*ca->HWAddr)
 253                         );
 254                 if( ca->WaitingCount == 0 )
 255                         last_unused = ca;
 256                 pnp = &ca->Next;
 257
 258                 // 2. If found, set the cache and poke waiting threads
 259                 if( memcmp(L3Addr, ca->L3Addr, addrsize) == 0 )
 260                 {
 261                         if( ca->WaitingCount )
 262                         {
 263                                 memcpy(ca->HWAddr, HWAddr, sizeof(tMacAddr));
 264                                 Semaphore_Signal(&ca->WaitingSem, INT_MAX);
 265                                 LOG("Found and cached");
 266                         }
 267                         else if( memcmp(HWAddr, ca->HWAddr, sizeof(tMacAddr)) )
 268                         {
 269                                 LOG("Differs to cache");
 270                         }
 271                         else
 272                         {
 273                                 LOG("Already known");
 274                         }
 275                         Mutex_Release(&cache->Lock);
 276                         return ;
 277                 }
 278         }
 279         // No existing entry, cache just in case
 280         if( cache->nAddrs < cache->MaxSize )
 281         {
 282                 // Create new
 283                 cache->nAddrs ++;
 284                 tHWAddrCachedAddr *ca = calloc(1,sizeof(tHWAddrCachedAddr)+addrsize+sizeof(tMacAddr));
 285                 *pnp = ca;
 286                 ca->L3Addr = ca+1;
 287                 ca->HWAddr = (void*)( (char*)ca->L3Addr + addrsize );
 288                 memcpy(ca->L3Addr, L3Addr, addrsize);
 289                 memcpy(ca->HWAddr, HWAddr, sizeof(tMacAddr));
 290                 LOG("Cache in new entry");
 291         }
 292         else if( last_unused )
 293         {
 294                 tHWAddrCachedAddr *ca = last_unused;
 295                 memcpy(ca->L3Addr, L3Addr, addrsize);
 296                 memcpy(ca->HWAddr, HWAddr, sizeof(tMacAddr));
 297                 // Maintain position
 298                 LOG("Cache in old entry");
 299         }
 300         else
 301         {
 302                 // None unused! What is this madness?
 303                 LOG("Not cached... cache being thrashed?");
 304         }
 305         Mutex_Release(&cache->Lock);
 306 }