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
22static uint32_t
23masked_address32 (uint32_t addr, uint8_t len)
24{
25  u32 a = ntohl(addr);
26  return htonl(len == 32 ? a : a & ~(~0u >> len));
27}
28static uint64_t
29masked_address64 (uint64_t addr, uint8_t len)
30{
31  return len == 64 ? addr : addr & ~(~0ull >> len);
32}
33
34static void
35lpm_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
59static void
60lpm_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
73static u32
74lpm_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
93static int
94lpm_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
108static u32
109lpm_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
123static void
124lpm_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
138static void
139lpm_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
156lpm_t *
157lpm_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}
182