src/plugins/map/lpm.c

   1 /*
   2  * Copyright (c) 2018 Cisco and/or its affiliates.
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  * You may obtain a copy of the License at:
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   9  * Unless required by applicable law or agreed to in writing, software
  10  * distributed under the License is distributed on an "AS IS" BASIS,
  11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12  * See the License for the specific language governing permissions and
  13  * limitations under the License.
  14  */
  15
  16 #include "lpm.h"
  17 #include <vnet/ip/ip4_packet.h>
  18 #include <vnet/ip/ip6_packet.h>
  19 #include <arpa/inet.h>
  20 #include <vnet/ip/format.h>
  21
  22 static uint32_t
  23 masked_address32 (uint32_t addr, uint8_t len)
  24 {
  25   u32 a = ntohl(addr);
  26   return htonl(len == 32 ? a : a & ~(~0u >> len));
  27 }
  28 static uint64_t
  29 masked_address64 (uint64_t addr, uint8_t len)
  30 {
  31   /* This was originally causing non-64-bit masks to not match due to LSB vs
  32    * MSB masking (0s at the head of the value) Probably needs some corner case
  33    * checking in case my masking logic was off [dgeist]
  34    *
  35    * return len == 64 ? addr : addr & ~(~0ull >> len);
  36    */
  37   return len == 64 ? addr : addr & ((1ull << (len)) - 1);
  38 }
  39
  40 static void
  41 lpm_32_add (lpm_t *lpm, void *addr_v, u8 pfxlen,
  42             u32 value)
  43 {
  44   uword * hash, * result;
  45   u32 key;
  46   ip4_address_t *addr = addr_v;
  47   key = masked_address32(addr->data_u32, pfxlen);
  48   hash = lpm->hash[pfxlen];
  49   result = hash_get (hash, key);
  50   if (result) /* Entry exists */
  51     clib_warning("%U/%d already exists in table for domain %d",
  52                  format_ip4_address, addr, pfxlen, result[0]);
  53
  54   /*
  55    * adding a new entry
  56    */
  57   if (hash == NULL) {
  58     hash = hash_create (32 /* elts */, sizeof (uword));
  59     hash_set_flags (hash, HASH_FLAG_NO_AUTO_SHRINK);
  60   }
  61   hash = hash_set(hash, key, value);
  62   lpm->hash[pfxlen] = hash;
  63 }
  64
  65 static void
  66 lpm_32_delete (lpm_t *lpm, void *addr_v, u8 pfxlen)
  67 {
  68   uword * hash, * result;
  69   u32 key;
  70   ip4_address_t *addr = addr_v;
  71   key = masked_address32(addr->data_u32, pfxlen);
  72   hash = lpm->hash[pfxlen];
  73   result = hash_get (hash, key);
  74   if (result)
  75     hash_unset(hash, key);
  76   lpm->hash[pfxlen] = hash;
  77 }
  78
  79 static u32
  80 lpm_32_lookup (lpm_t *lpm, void *addr_v, u8 pfxlen)
  81 {
  82   uword * hash, * result;
  83   i32 mask_len;
  84   u32 key;
  85   ip4_address_t *addr = addr_v;
  86   for (mask_len = pfxlen; mask_len >= 0; mask_len--) {
  87     hash = lpm->hash[mask_len];
  88     if (hash) {
  89       key = masked_address32(addr->data_u32, mask_len);
  90       result = hash_get (hash, key);
  91       if (result != NULL) {
  92         return (result[0]);
  93       }
  94     }
  95   }
  96   return (~0);
  97 }
  98
  99 static int
 100 lpm_128_lookup_core (lpm_t *lpm, ip6_address_t *addr, u8 pfxlen, u32 *value)
 101 {
 102   BVT(clib_bihash_kv) kv, v;
 103   int rv;
 104   kv.key[0] = masked_address64(addr->as_u64[0], pfxlen > 64 ? 64 : pfxlen);
 105   kv.key[1] = masked_address64(addr->as_u64[1], pfxlen > 64 ? pfxlen - 64 : 0);
 106   kv.key[2] = pfxlen;
 107   rv = BV(clib_bihash_search_inline_2)(&lpm->bihash, &kv, &v);
 108   if (rv != 0)
 109     return -1;
 110   *value = v.value;
 111   return 0;
 112 }
 113
 114 static u32
 115 lpm_128_lookup (lpm_t *lpm, void *addr_v, u8 pfxlen)
 116 {
 117   ip6_address_t *addr = addr_v;
 118   int i = 0, rv;
 119   u32 value;
 120   clib_bitmap_foreach (i, lpm->prefix_lengths_bitmap)
 121      {
 122       rv = lpm_128_lookup_core(lpm, addr, i, &value);
 123       if (rv == 0)
 124         return value;
 125     }
 126   return ~0;
 127 }
 128
 129 static void
 130 lpm_128_add (lpm_t *lpm, void *addr_v, u8 pfxlen, u32 value)
 131 {
 132   BVT(clib_bihash_kv) kv;
 133   ip6_address_t *addr = addr_v;
 134
 135   /* This is a quick hack. It works for pfxlen < 64 but needs validation for
 136    * other [dgeist]
 137    *
 138    * kv.key[0] = masked_address64(addr->as_u64[0], pfxlen > 64 ? 64 : pfxlen);
 139    */
 140   kv.key[0] = masked_address64 (addr->as_u64[0], pfxlen > 64 ? 64 : 64);
 141   kv.key[1] = masked_address64(addr->as_u64[1], pfxlen > 64 ? pfxlen - 64 : 0);
 142   kv.key[2] = pfxlen;
 143   kv.value = value;
 144   BV(clib_bihash_add_del)(&lpm->bihash, &kv, 1);
 145   lpm->prefix_length_refcount[pfxlen]++;
 146   /* Populating the lengths bitmap table with prefix of 48 instead of 80
 147    * (128 - 48) [dgeist]
 148    *
 149    * lpm->prefix_lengths_bitmap = clib_bitmap_set (
 150    *   lpm->prefix_lengths_bitmap, 128 - pfxlen, 1);
 151    */
 152   lpm->prefix_lengths_bitmap = clib_bitmap_set (
 153     lpm->prefix_lengths_bitmap, pfxlen > 64 ? 128 - pfxlen : pfxlen, 1);
 154 }
 155
 156 static void
 157 lpm_128_delete (lpm_t *lpm, void *addr_v, u8 pfxlen)
 158 {
 159   ip6_address_t *addr = addr_v;
 160   BVT(clib_bihash_kv) kv;
 161   kv.key[0] = masked_address64(addr->as_u64[0], pfxlen > 64 ? 64 : pfxlen);
 162   kv.key[1] = masked_address64(addr->as_u64[1], pfxlen > 64 ? pfxlen - 64 : 0);
 163   kv.key[2] = pfxlen;
 164   BV(clib_bihash_add_del)(&lpm->bihash, &kv, 0);
 165
 166   /* refcount accounting */
 167   ASSERT (lpm->prefix_length_refcount[pfxlen] > 0);
 168   if (--lpm->prefix_length_refcount[pfxlen] == 0) {
 169       lpm->prefix_lengths_bitmap =
 170         clib_bitmap_set (lpm->prefix_lengths_bitmap, 128 - pfxlen, 0);
 171   }
 172 }
 173
 174 lpm_t *
 175 lpm_table_init (enum lpm_type_e lpm_type)
 176 {
 177   lpm_t * lpm = clib_mem_alloc(sizeof(*lpm));
 178   memset(lpm, 0, sizeof(*lpm));
 179
 180   switch (lpm_type) {
 181   case LPM_TYPE_KEY32:
 182     lpm->add = lpm_32_add;
 183     lpm->delete = lpm_32_delete;
 184     lpm->lookup = lpm_32_lookup;
 185     break;
 186   case LPM_TYPE_KEY128:
 187     lpm->add = lpm_128_add;
 188     lpm->delete = lpm_128_delete;
 189     lpm->lookup = lpm_128_lookup;
 190     /* Make bihash sizes configurable */
 191     BV (clib_bihash_init) (&(lpm->bihash),
 192                            "LPM 128", 64*1024, 32<<20);
 193
 194     break;
 195   default:
 196     ASSERT(0);
 197   }
 198   return lpm;
 199 }