Ip4Route.c

Go to the documentation of this file.

 
#include "Ip4Impl.h"
 
IP4_ROUTE_ENTRY *
Ip4CreateRouteEntry (
  IN IP4_ADDR  Dest,
  IN IP4_ADDR  Netmask,
  IN IP4_ADDR  GateWay
  )
{
  IP4_ROUTE_ENTRY  *RtEntry;
 
  RtEntry = AllocatePool (sizeof (IP4_ROUTE_ENTRY));
 
  if (RtEntry == NULL) {
    return NULL;
  }
 
  InitializeListHead (&RtEntry->Link);
 
  RtEntry->RefCnt  = 1;
  RtEntry->Dest    = Dest;
  RtEntry->Netmask = Netmask;
  RtEntry->NextHop = GateWay;
  RtEntry->Flag    = 0;
 
  return RtEntry;
}
 
VOID
Ip4FreeRouteEntry (
  IN IP4_ROUTE_ENTRY  *RtEntry
  )
{
  ASSERT (RtEntry->RefCnt > 0);
 
  if (--RtEntry->RefCnt == 0) {
    FreePool (RtEntry);
  }
}
 
IP4_ROUTE_CACHE_ENTRY *
Ip4CreateRouteCacheEntry (
  IN IP4_ADDR  Dst,
  IN IP4_ADDR  Src,
  IN IP4_ADDR  GateWay,
  IN UINTN     Tag
  )
{
  IP4_ROUTE_CACHE_ENTRY  *RtCacheEntry;
 
  RtCacheEntry = AllocatePool (sizeof (IP4_ROUTE_CACHE_ENTRY));
 
  if (RtCacheEntry == NULL) {
    return NULL;
  }
 
  InitializeListHead (&RtCacheEntry->Link);
 
  RtCacheEntry->RefCnt  = 1;
  RtCacheEntry->Dest    = Dst;
  RtCacheEntry->Src     = Src;
  RtCacheEntry->NextHop = GateWay;
  RtCacheEntry->Tag     = Tag;
 
  return RtCacheEntry;
}
 
VOID
Ip4FreeRouteCacheEntry (
  IN IP4_ROUTE_CACHE_ENTRY  *RtCacheEntry
  )
{
  ASSERT (RtCacheEntry->RefCnt > 0);
 
  if (--RtCacheEntry->RefCnt == 0) {
    FreePool (RtCacheEntry);
  }
}
 
VOID
Ip4InitRouteCache (
  IN OUT IP4_ROUTE_CACHE  *RtCache
  )
{
  UINT32  Index;
 
  for (Index = 0; Index < IP4_ROUTE_CACHE_HASH_VALUE; Index++) {
    InitializeListHead (&(RtCache->CacheBucket[Index]));
  }
}
 
VOID
Ip4CleanRouteCache (
  IN IP4_ROUTE_CACHE  *RtCache
  )
{
  LIST_ENTRY             *Entry;
  LIST_ENTRY             *Next;
  IP4_ROUTE_CACHE_ENTRY  *RtCacheEntry;
  UINT32                 Index;
 
  for (Index = 0; Index < IP4_ROUTE_CACHE_HASH_VALUE; Index++) {
    NET_LIST_FOR_EACH_SAFE (Entry, Next, &(RtCache->CacheBucket[Index])) {
      RtCacheEntry = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_CACHE_ENTRY, Link);
 
      RemoveEntryList (Entry);
      Ip4FreeRouteCacheEntry (RtCacheEntry);
    }
  }
}
 
IP4_ROUTE_TABLE *
Ip4CreateRouteTable (
  VOID
  )
{
  IP4_ROUTE_TABLE  *RtTable;
  UINT32           Index;
 
  RtTable = AllocatePool (sizeof (IP4_ROUTE_TABLE));
 
  if (RtTable == NULL) {
    return NULL;
  }
 
  RtTable->RefCnt   = 1;
  RtTable->TotalNum = 0;
 
  for (Index = 0; Index <= IP4_MASK_MAX; Index++) {
    InitializeListHead (&(RtTable->RouteArea[Index]));
  }
 
  RtTable->Next = NULL;
 
  Ip4InitRouteCache (&RtTable->Cache);
  return RtTable;
}
 
VOID
Ip4FreeRouteTable (
  IN IP4_ROUTE_TABLE  *RtTable
  )
{
  LIST_ENTRY       *Entry;
  LIST_ENTRY       *Next;
  IP4_ROUTE_ENTRY  *RtEntry;
  UINT32           Index;
 
  ASSERT (RtTable->RefCnt > 0);
 
  if (--RtTable->RefCnt > 0) {
    return;
  }
 
  //
  // Free all the route table entry and its route cache.
  //
  for (Index = 0; Index <= IP4_MASK_MAX; Index++) {
    NET_LIST_FOR_EACH_SAFE (Entry, Next, &(RtTable->RouteArea[Index])) {
      RtEntry = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_ENTRY, Link);
 
      RemoveEntryList (Entry);
      Ip4FreeRouteEntry (RtEntry);
    }
  }
 
  Ip4CleanRouteCache (&RtTable->Cache);
 
  FreePool (RtTable);
}
 
VOID
Ip4PurgeRouteCache (
  IN OUT IP4_ROUTE_CACHE  *RtCache,
  IN     UINTN            Tag
  )
{
  LIST_ENTRY             *Entry;
  LIST_ENTRY             *Next;
  IP4_ROUTE_CACHE_ENTRY  *RtCacheEntry;
  UINT32                 Index;
 
  for (Index = 0; Index < IP4_ROUTE_CACHE_HASH_VALUE; Index++) {
    NET_LIST_FOR_EACH_SAFE (Entry, Next, &RtCache->CacheBucket[Index]) {
      RtCacheEntry = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_CACHE_ENTRY, Link);
 
      if (RtCacheEntry->Tag == Tag) {
        RemoveEntryList (Entry);
        Ip4FreeRouteCacheEntry (RtCacheEntry);
      }
    }
  }
}
 
EFI_STATUS
Ip4AddRoute (
  IN OUT IP4_ROUTE_TABLE  *RtTable,
  IN     IP4_ADDR         Dest,
  IN     IP4_ADDR         Netmask,
  IN     IP4_ADDR         Gateway
  )
{
  LIST_ENTRY       *Head;
  LIST_ENTRY       *Entry;
  IP4_ROUTE_ENTRY  *RtEntry;
 
  //
  // All the route entries with the same netmask length are
  // linke to the same route area
  //
  Head = &(RtTable->RouteArea[NetGetMaskLength (Netmask)]);
 
  //
  // First check whether the route exists
  //
  NET_LIST_FOR_EACH (Entry, Head) {
    RtEntry = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_ENTRY, Link);
 
    if (IP4_NET_EQUAL (RtEntry->Dest, Dest, Netmask) && (RtEntry->NextHop == Gateway)) {
      return EFI_ACCESS_DENIED;
    }
  }
 
  //
  // Create a route entry and insert it to the route area.
  //
  RtEntry = Ip4CreateRouteEntry (Dest, Netmask, Gateway);
 
  if (RtEntry == NULL) {
    return EFI_OUT_OF_RESOURCES;
  }
 
  if (Gateway == IP4_ALLZERO_ADDRESS) {
    RtEntry->Flag = IP4_DIRECT_ROUTE;
  }
 
  InsertHeadList (Head, &RtEntry->Link);
  RtTable->TotalNum++;
 
  return EFI_SUCCESS;
}
 
EFI_STATUS
Ip4DelRoute (
  IN OUT IP4_ROUTE_TABLE  *RtTable,
  IN     IP4_ADDR         Dest,
  IN     IP4_ADDR         Netmask,
  IN     IP4_ADDR         Gateway
  )
{
  LIST_ENTRY       *Head;
  LIST_ENTRY       *Entry;
  LIST_ENTRY       *Next;
  IP4_ROUTE_ENTRY  *RtEntry;
 
  Head = &(RtTable->RouteArea[NetGetMaskLength (Netmask)]);
 
  NET_LIST_FOR_EACH_SAFE (Entry, Next, Head) {
    RtEntry = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_ENTRY, Link);
 
    if (IP4_NET_EQUAL (RtEntry->Dest, Dest, Netmask) && (RtEntry->NextHop == Gateway)) {
      Ip4PurgeRouteCache (&RtTable->Cache, (UINTN)RtEntry);
      RemoveEntryList (Entry);
      Ip4FreeRouteEntry (RtEntry);
 
      RtTable->TotalNum--;
      return EFI_SUCCESS;
    }
  }
 
  return EFI_NOT_FOUND;
}
 
IP4_ROUTE_CACHE_ENTRY *
Ip4FindRouteCache (
  IN IP4_ROUTE_TABLE  *RtTable,
  IN IP4_ADDR         Dest,
  IN IP4_ADDR         Src
  )
{
  LIST_ENTRY             *Entry;
  IP4_ROUTE_CACHE_ENTRY  *RtCacheEntry;
  UINT32                 Index;
 
  Index = IP4_ROUTE_CACHE_HASH (Dest, Src);
 
  NET_LIST_FOR_EACH (Entry, &RtTable->Cache.CacheBucket[Index]) {
    RtCacheEntry = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_CACHE_ENTRY, Link);
 
    if ((RtCacheEntry->Dest == Dest) && (RtCacheEntry->Src == Src)) {
      NET_GET_REF (RtCacheEntry);
      return RtCacheEntry;
    }
  }
 
  return NULL;
}
 
IP4_ROUTE_ENTRY *
Ip4FindRouteEntry (
  IN IP4_ROUTE_TABLE  *RtTable,
  IN IP4_ADDR         Dst
  )
{
  LIST_ENTRY       *Entry;
  IP4_ROUTE_ENTRY  *RtEntry;
  IP4_ROUTE_TABLE  *Table;
  INTN             Index;
 
  RtEntry = NULL;
 
  for (Index = IP4_MASK_MAX; Index >= 0; Index--) {
    for (Table = RtTable; Table != NULL; Table = Table->Next) {
      NET_LIST_FOR_EACH (Entry, &Table->RouteArea[Index]) {
        RtEntry = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_ENTRY, Link);
 
        if (IP4_NET_EQUAL (RtEntry->Dest, Dst, RtEntry->Netmask)) {
          NET_GET_REF (RtEntry);
          return RtEntry;
        }
      }
    }
  }
 
  return NULL;
}
 
IP4_ROUTE_CACHE_ENTRY *
Ip4Route (
  IN IP4_ROUTE_TABLE  *RtTable,
  IN IP4_ADDR         Dest,
  IN IP4_ADDR         Src,
  IN IP4_ADDR         SubnetMask,
  IN BOOLEAN          AlwaysTryDestAddr
  )
{
  LIST_ENTRY             *Head;
  LIST_ENTRY             *Entry;
  LIST_ENTRY             *Next;
  IP4_ROUTE_CACHE_ENTRY  *RtCacheEntry;
  IP4_ROUTE_CACHE_ENTRY  *Cache;
  IP4_ROUTE_ENTRY        *RtEntry;
  IP4_ADDR               NextHop;
  UINT32                 Count;
 
  ASSERT (RtTable != NULL);
 
  Head         = &RtTable->Cache.CacheBucket[IP4_ROUTE_CACHE_HASH (Dest, Src)];
  RtCacheEntry = Ip4FindRouteCache (RtTable, Dest, Src);
 
  //
  // If found, promote the cache entry to the head of the hash bucket. LRU
  //
  if (RtCacheEntry != NULL) {
    RemoveEntryList (&RtCacheEntry->Link);
    InsertHeadList (Head, &RtCacheEntry->Link);
    return RtCacheEntry;
  }
 
  //
  // Search the route table for the most specific route
  //
  RtEntry = Ip4FindRouteEntry (RtTable, Dest);
 
  if (RtEntry == NULL) {
    if (SubnetMask != IP4_ALLONE_ADDRESS) {
      return NULL;
    } else if (!AlwaysTryDestAddr) {
      return NULL;
    }
  }
 
  //
  // Found a route to the Dest, if it is a direct route, the packet
  // will be sent directly to the destination, such as for connected
  // network. Otherwise, it is an indirect route, the packet will be
  // sent to the next hop router.
  //
  // When using /32 subnet mask, the packet will always be sent to the direct
  // destination first, if we can't find a matching route cache.
  //
  if ((SubnetMask == IP4_ALLONE_ADDRESS) || ((RtEntry->Flag & IP4_DIRECT_ROUTE) != 0)) {
    NextHop = Dest;
  } else {
    NextHop = RtEntry->NextHop;
  }
 
  if (RtEntry != NULL) {
    Ip4FreeRouteEntry (RtEntry);
  }
 
  //
  // Create a route cache entry, and tag it as spawned from this route entry
  // For /32 subnet mask, the default route in RtEntry will be used if failed
  // to send the packet to driect destination address.
  //
  RtCacheEntry = Ip4CreateRouteCacheEntry (Dest, Src, NextHop, (UINTN)RtEntry);
 
  if (RtCacheEntry == NULL) {
    return NULL;
  }
 
  InsertHeadList (Head, &RtCacheEntry->Link);
  NET_GET_REF (RtCacheEntry);
 
  //
  // Each bucket of route cache can contain at most 64 entries.
  // Remove the entries at the tail of the bucket. These entries
  // are likely to be used least.
  //
  Count = 0;
  NET_LIST_FOR_EACH_SAFE (Entry, Next, Head) {
    if (++Count < IP4_ROUTE_CACHE_MAX) {
      continue;
    }
 
    Cache = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_CACHE_ENTRY, Link);
 
    RemoveEntryList (Entry);
    Ip4FreeRouteCacheEntry (Cache);
  }
 
  return RtCacheEntry;
}
 
EFI_STATUS
Ip4BuildEfiRouteTable (
  IN IP4_PROTOCOL  *IpInstance
  )
{
  LIST_ENTRY           *Entry;
  IP4_ROUTE_TABLE      *RtTable;
  IP4_ROUTE_ENTRY      *RtEntry;
  EFI_IP4_ROUTE_TABLE  *Table;
  UINT32               Count;
  INT32                Index;
 
  RtTable = IpInstance->RouteTable;
 
  if (IpInstance->EfiRouteTable != NULL) {
    FreePool (IpInstance->EfiRouteTable);
 
    IpInstance->EfiRouteTable = NULL;
    IpInstance->EfiRouteCount = 0;
  }
 
  Count = RtTable->TotalNum;
 
  if (RtTable->Next != NULL) {
    Count += RtTable->Next->TotalNum;
  }
 
  if (Count == 0) {
    return EFI_SUCCESS;
  }
 
  Table = AllocatePool (sizeof (EFI_IP4_ROUTE_TABLE) * Count);
 
  if (Table == NULL) {
    return EFI_OUT_OF_RESOURCES;
  }
 
  //
  // Copy the route entry to EFI route table. Keep the order of
  // route entry copied from most specific to default route. That
  // is, interlevel the route entry from the instance's route area
  // and those from the default route table's route area.
  //
  Count = 0;
 
  for (Index = IP4_MASK_MAX; Index >= 0; Index--) {
    for (RtTable = IpInstance->RouteTable; RtTable != NULL; RtTable = RtTable->Next) {
      NET_LIST_FOR_EACH (Entry, &(RtTable->RouteArea[Index])) {
        RtEntry = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_ENTRY, Link);
 
        EFI_IP4 (Table[Count].SubnetAddress)  = HTONL (RtEntry->Dest & RtEntry->Netmask);
        EFI_IP4 (Table[Count].SubnetMask)     = HTONL (RtEntry->Netmask);
        EFI_IP4 (Table[Count].GatewayAddress) = HTONL (RtEntry->NextHop);
 
        Count++;
      }
    }
  }
 
  IpInstance->EfiRouteTable = Table;
  IpInstance->EfiRouteCount = Count;
  return EFI_SUCCESS;
}