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   return len == 64 ? addr : addr & ~(~0ull >> len);
  32 }
  33
  34 static void
  35 lpm_32_add (lpm_t *lpm, void *addr_v, u8 pfxlen,
  36             u32 value)
  37 {
  38   uword * hash, * result;
  39   u32 key;
  40   ip4_address_t *addr = addr_v;
  41   key = masked_address32(addr->data_u32, pfxlen);
  42   hash = lpm->hash[pfxlen];
  43   result = hash_get (hash, key);
  44   if (result) /* Entry exists */
  45     clib_warning("%U/%d already exists in table for domain %d",
  46                  format_ip4_address, addr, pfxlen, result[0]);
  47
  48   /*
  49    * adding a new entry
  50    */
  51   if (hash == NULL) {
  52     hash = hash_create (32 /* elts */, sizeof (uword));
  53     hash_set_flags (hash, HASH_FLAG_NO_AUTO_SHRINK);
  54   }
  55   hash = hash_set(hash, key, value);
  56   lpm->hash[pfxlen] = hash;
  57 }
  58
  59 static void
  60 lpm_32_delete (lpm_t *lpm, void *addr_v, u8 pfxlen)
  61 {
  62   uword * hash, * result;
  63   u32 key;
  64   ip4_address_t *addr = addr_v;
  65   key = masked_address32(addr->data_u32, pfxlen);
  66   hash = lpm->hash[pfxlen];
  67   result = hash_get (hash, key);
  68   if (result)
  69     hash_unset(hash, key);
  70   lpm->hash[pfxlen] = hash;
  71 }
  72
  73 static u32
  74 lpm_32_lookup (lpm_t *lpm, void *addr_v, u8 pfxlen)
  75 {
  76   uword * hash, * result;
  77   i32 mask_len;
  78   u32 key;
  79   ip4_address_t *addr = addr_v;
  80   for (mask_len = pfxlen; mask_len >= 0; mask_len--) {
  81     hash = lpm->hash[mask_len];
  82     if (hash) {
  83       key = masked_address32(addr->data_u32, mask_len);
  84       result = hash_get (hash, key);
  85       if (result != NULL) {
  86         return (result[0]);
  87       }
  88     }
  89   }
  90   return (~0);
  91 }
  92
  93 static int
  94 lpm_128_lookup_core (lpm_t *lpm, ip6_address_t *addr, u8 pfxlen, u32 *value)
  95 {
  96   BVT(clib_bihash_kv) kv, v;
  97   int rv;
  98   kv.key[0] = masked_address64(addr->as_u64[0], pfxlen > 64 ? 64 : pfxlen);
  99   kv.key[1] = masked_address64(addr->as_u64[1], pfxlen > 64 ? pfxlen - 64 : 0);
 100   kv.key[2] = pfxlen;
 101   rv = BV(clib_bihash_search_inline_2)(&lpm->bihash, &kv, &v);
 102   if (rv != 0)
 103     return -1;
 104   *value = v.value;
 105   return 0;
 106 }
 107
 108 static u32
 109 lpm_128_lookup (lpm_t *lpm, void *addr_v, u8 pfxlen)
 110 {
 111   ip6_address_t *addr = addr_v;
 112   int i = 0, rv;
 113   u32 value;
 114   clib_bitmap_foreach (i, lpm->prefix_lengths_bitmap,
 115     ({
 116       rv = lpm_128_lookup_core(lpm, addr, i, &value);
 117       if (rv == 0)
 118         return value;
 119     }));
 120   return ~0;
 121 }
 122
 123 static void
 124 lpm_128_add (lpm_t *lpm, void *addr_v, u8 pfxlen, u32 value)
 125 {
 126   BVT(clib_bihash_kv) kv;
 127   ip6_address_t *addr = addr_v;
 128
 129   kv.key[0] = masked_address64(addr->as_u64[0], pfxlen > 64 ? 64 : pfxlen);
 130   kv.key[1] = masked_address64(addr->as_u64[1], pfxlen > 64 ? pfxlen - 64 : 0);
 131   kv.key[2] = pfxlen;
 132   kv.value = value;
 133   BV(clib_bihash_add_del)(&lpm->bihash, &kv, 1);
 134   lpm->prefix_length_refcount[pfxlen]++;
 135   lpm->prefix_lengths_bitmap = clib_bitmap_set (lpm->prefix_lengths_bitmap, 128 - pfxlen, 1);
 136 }
 137
 138 static void
 139 lpm_128_delete (lpm_t *lpm, void *addr_v, u8 pfxlen)
 140 {
 141   ip6_address_t *addr = addr_v;
 142   BVT(clib_bihash_kv) kv;
 143   kv.key[0] = masked_address64(addr->as_u64[0], pfxlen > 64 ? 64 : pfxlen);
 144   kv.key[1] = masked_address64(addr->as_u64[1], pfxlen > 64 ? pfxlen - 64 : 0);
 145   kv.key[2] = pfxlen;
 146   BV(clib_bihash_add_del)(&lpm->bihash, &kv, 0);
 147
 148   /* refcount accounting */
 149   ASSERT (lpm->prefix_length_refcount[pfxlen] > 0);
 150   if (--lpm->prefix_length_refcount[pfxlen] == 0) {
 151     lpm->prefix_lengths_bitmap = clib_bitmap_set (lpm->prefix_lengths_bitmap,
 152                                                   128 - pfxlen, 0);
 153   }
 154 }
 155
 156 lpm_t *
 157 lpm_table_init (enum lpm_type_e lpm_type)
 158 {
 159   lpm_t * lpm = clib_mem_alloc(sizeof(*lpm));
 160   memset(lpm, 0, sizeof(*lpm));
 161
 162   switch (lpm_type) {
 163   case LPM_TYPE_KEY32:
 164     lpm->add = lpm_32_add;
 165     lpm->delete = lpm_32_delete;
 166     lpm->lookup = lpm_32_lookup;
 167     break;
 168   case LPM_TYPE_KEY128:
 169     lpm->add = lpm_128_add;
 170     lpm->delete = lpm_128_delete;
 171     lpm->lookup = lpm_128_lookup;
 172     /* Make bihash sizes configurable */
 173     BV (clib_bihash_init) (&(lpm->bihash),
 174                            "LPM 128", 64*1024, 32<<20);
 175
 176     break;
 177   default:
 178     ASSERT(0);
 179   }
 180   return lpm;
 181 }