third_party/lwip/repo/lwip/src/core/ipv6/ip6_route_table.c

   1 /**
   2  * @file
   3  *
   4  * IPv6 static route table.
   5  */
   6
   7 /*
   8  * Copyright (c) 2015 Nest Labs, Inc.
   9  * All rights reserved.
  10  *
  11  * Redistribution and use in source and binary forms, with or without modification,
  12  * are permitted provided that the following conditions are met:
  13  *
  14  * 1. Redistributions of source code must retain the above copyright notice,
  15  *    this list of conditions and the following disclaimer.
  16  * 2. Redistributions in binary form must reproduce the above copyright notice,
  17  *    this list of conditions and the following disclaimer in the documentation
  18  *    and/or other materials provided with the distribution.
  19  * 3. The name of the author may not be used to endorse or promote products
  20  *    derived from this software without specific prior written permission.
  21  *
  22  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED
  23  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
  24  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT
  25  * SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  26  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
  27  * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  28  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  29  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
  30  * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY
  31  * OF SUCH DAMAGE.
  32  *
  33  * Author: Pradip De <pde@nestlabs.com>
  34  *
  35  *
  36  * Please coordinate changes and requests with Pradip De
  37  * <pde@nestlabs.com>
  38  */
  39
  40 #include "lwip/opt.h"
  41
  42 #if LWIP_IPV6  /* don't build if not configured for use in lwipopts.h */
  43
  44 #include "lwip/def.h"
  45 #include "lwip/mem.h"
  46 #include "lwip/netif.h"
  47 #include "lwip/ip6.h"
  48 #include "lwip/ip6_route_table.h"
  49 #include "lwip/ip6_addr.h"
  50 #include "lwip/nd6.h"
  51 #include "lwip/debug.h"
  52 #include "lwip/stats.h"
  53
  54 #include "string.h"
  55
  56 #if LWIP_IPV6_ROUTE_TABLE_SUPPORT
  57
  58 static struct ip6_route_entry static_route_table[LWIP_IPV6_NUM_ROUTE_ENTRIES];
  59
  60 /**
  61  * Add the ip6 prefix route and target netif into the static route table while
  62  * keeping all entries sorted in decreasing order of prefix length.
  63  * 1. Search from the last entry up to find the correct slot to insert while
  64  *    moving entries one position down to create room.
  65  * 2. Insert into empty slot created.
  66  *
  67  * Subsequently, a linear search down the list can be performed to retrieve a
  68  * matching route entry for a Longest Prefix Match.
  69  *
  70  * @param ip6_prefix the route prefix entry to add.
  71  * @param netif pointer to target netif.
  72  * @param gateway the gateway address to use to send through. Has to be link local.
  73  * @param index return value argument of index where route entry was added in table.
  74  * @return ERR_OK  if addition was successful.
  75  *         ERR_MEM if table is already full.
  76  *         ERR_ARG if passed argument is bad or route already exists in table.
  77  */
  78 err_t
  79 ip6_add_route_entry(struct ip6_prefix *ip6_prefix, struct netif *netif, ip6_addr_t *gateway, s8_t *index)
  80 {
  81   int i = -1;
  82   err_t retval = ERR_OK;
  83
  84   if (!ip6_prefix_valid(ip6_prefix->prefix_len) || (netif == NULL)) {
  85     retval = ERR_ARG;
  86     goto exit;
  87   }
  88
  89   /* Check if an entry already exists with matching prefix; If so, replace it. */
  90   for (i = 0; i < LWIP_IPV6_NUM_ROUTE_ENTRIES; i++) {
  91     if ((ip6_prefix->prefix_len == static_route_table[i].prefix.prefix_len) &&
  92         memcmp(&ip6_prefix->addr, &static_route_table[i].prefix.addr,
  93                ip6_prefix->prefix_len / 8) == 0) {
  94       //Prefix matches; replace the netif with the one being added.
  95       goto insert;
  96     }
  97   }
  98
  99   /* Check if the table is full */
 100   if (static_route_table[LWIP_IPV6_NUM_ROUTE_ENTRIES - 1].netif != NULL) {
 101     retval = ERR_MEM;
 102     goto exit;
 103   }
 104
 105   /* Shift all entries down the table until slot is found */
 106   for (i = LWIP_IPV6_NUM_ROUTE_ENTRIES - 1;
 107        i > 0 && (ip6_prefix->prefix_len > static_route_table[i - 1].prefix.prefix_len); i--) {
 108     SMEMCPY(&static_route_table[i], &static_route_table[i - 1], sizeof(struct ip6_route_entry));
 109   }
 110
 111 insert:
 112   /* Insert into the slot selected */
 113   SMEMCPY(&static_route_table[i].prefix, ip6_prefix, sizeof(struct ip6_prefix));
 114   static_route_table[i].netif = netif;
 115
 116   /* Add gateway to route table */
 117   static_route_table[i].gateway = gateway;
 118
 119   if (index != NULL) {
 120     *index = i;
 121   }
 122
 123 exit:
 124   return retval;
 125 }
 126
 127 /**
 128  * Removes the route entry from the static route table.
 129  *
 130  * @param ip6_prefix the route prefix entry to delete.
 131  */
 132 void
 133 ip6_remove_route_entry(struct ip6_prefix *ip6_prefix)
 134 {
 135   int i, pos = -1;
 136
 137   for (i = 0; i < LWIP_IPV6_NUM_ROUTE_ENTRIES; i++) {
 138     /* compare prefix to find position to delete */
 139     if (ip6_prefix->prefix_len == static_route_table[i].prefix.prefix_len &&
 140         memcmp(&ip6_prefix->addr, &static_route_table[i].prefix.addr,
 141                ip6_prefix->prefix_len / 8) == 0) {
 142       pos = i;
 143       break;
 144     }
 145   }
 146
 147   if (pos >= 0) {
 148     /* Shift everything beyond pos one slot up */
 149     for (i = pos; i < LWIP_IPV6_NUM_ROUTE_ENTRIES - 1; i++) {
 150       SMEMCPY(&static_route_table[i], &static_route_table[i+1], sizeof(struct ip6_route_entry));
 151       if (static_route_table[i].netif == NULL) {
 152         break;
 153       }
 154     }
 155     /* Zero the remaining entries */
 156     for (; i < LWIP_IPV6_NUM_ROUTE_ENTRIES; i++) {
 157       ip6_addr_set_zero((&static_route_table[i].prefix.addr));
 158       static_route_table[i].netif = NULL;
 159     }
 160   }
 161
 162   return;
 163 }
 164
 165 /**
 166  * Finds the appropriate route entry in the static route table corresponding to the given
 167  * destination IPv6 address. Since the entries in the route table are kept sorted in decreasing
 168  * order of prefix length, a linear search down the list is performed to retrieve a matching
 169  * index.
 170  *
 171  * @param ip6_dest_addr the destination address to match
 172  * @return the index of the found route entry; -1 if not found.
 173  */
 174 s8_t
 175 ip6_find_route_entry(const ip6_addr_t *ip6_dest_addr)
 176 {
 177   int i, index = -1;
 178
 179   /* Search prefix in the sorted(decreasing order of prefix length) list */
 180   for(i = 0; i < LWIP_IPV6_NUM_ROUTE_ENTRIES; i++) {
 181     if (memcmp(ip6_dest_addr, &static_route_table[i].prefix.addr,
 182         static_route_table[i].prefix.prefix_len / 8) == 0) {
 183       index = i;
 184       break;
 185     }
 186   }
 187
 188   return index;
 189 }
 190
 191 /**
 192  * Finds the appropriate network interface for a given IPv6 address from a routing table with
 193  * static IPv6 routes.
 194  *
 195  * @param src the source IPv6 address, if known
 196  * @param dest the destination IPv6 address for which to find the route
 197  * @return the netif on which to send to reach dest
 198  */
 199 struct netif *
 200 ip6_static_route(const ip6_addr_t *src, const ip6_addr_t *dest)
 201 {
 202
 203   int i;
 204   /* Perform table lookup */
 205   i = ip6_find_route_entry(dest);
 206
 207   if (i >= 0) {
 208     return static_route_table[i].netif;
 209   }
 210   else {
 211     return NULL;
 212   }
 213 }
 214
 215 /**
 216  * Finds the gateway IP6 address for a given destination IPv6 address and target netif
 217  * from a routing table with static IPv6 routes.
 218  *
 219  * @param netif the netif used for sending
 220  * @param dest the destination IPv6 address
 221  * @return the ip6 address of the gateway to forward packet to
 222  */
 223 ip6_addr_t *
 224 ip6_get_gateway(struct netif *netif, const ip6_addr_t *dest)
 225 {
 226   ip6_addr_t *ret_gw = NULL;
 227   const int i = ip6_find_route_entry(dest);
 228
 229   if (i >= 0) {
 230     if (static_route_table[i].gateway != NULL) {
 231       ret_gw = static_route_table[i].gateway;
 232     }
 233   }
 234
 235   return ret_gw;
 236 }
 237
 238 /**
 239  * Returns the top of the route table.
 240  * This should be used for debug printing only.
 241  *
 242  * @return the top of the route table.
 243  */
 244 struct ip6_route_entry *
 245 ip6_get_route_table(void)
 246 {
 247     return static_route_table;
 248 }
 249
 250 #endif /* LWIP_IPV6_ROUTE_TABLE_SUPPORT */
 251
 252 #endif /* LWIP_IPV6 */