FD.io VPP  v19.01.1-17-ge106252
Vector Packet Processing
lpm.c
Go to the documentation of this file.
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));
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
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;
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) {
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 }
static int lpm_128_lookup_core(lpm_t *lpm, ip6_address_t *addr, u8 pfxlen, u32 *value)
Definition: lpm.c:94
lpm_t * lpm_table_init(enum lpm_type_e lpm_type)
Definition: lpm.c:157
#define hash_set(h, key, value)
Definition: hash.h:255
#define hash_unset(h, key)
Definition: hash.h:261
a
Definition: bitmap.h:538
static uint32_t masked_address32(uint32_t addr, uint8_t len)
Definition: lpm.c:23
u64 as_u64[2]
Definition: ip6_packet.h:51
static void lpm_128_add(lpm_t *lpm, void *addr_v, u8 pfxlen, u32 value)
Definition: lpm.c:124
#define NULL
Definition: clib.h:58
int i
static uword * clib_bitmap_set(uword *ai, uword i, uword value)
Sets the ith bit of a bitmap to new_value Removes trailing zeros from the bitmap. ...
Definition: bitmap.h:167
vhost_vring_addr_t addr
Definition: vhost_user.h:121
unsigned char u8
Definition: types.h:56
format_function_t format_ip4_address
Definition: format.h:75
void(* add)(struct lpm_ *lpm, void *addr_v, u8 pfxlen, u32 value)
Definition: lpm.h:25
int clib_bihash_add_del(clib_bihash *h, clib_bihash_kv *add_v, int is_add)
Add or delete a (key,value) pair from a bi-hash table.
static BVT(clib_bihash)
Definition: adj_nbr.c:28
unsigned int u32
Definition: types.h:88
static void hash_set_flags(void *v, uword flags)
Definition: hash.h:153
u32(* lookup)(struct lpm_ *lpm, void *addr_v, u8 pfxlen)
Definition: lpm.h:27
lpm_type_e
Definition: lpm.h:19
Definition: lpm.h:24
#define hash_get(h, key)
Definition: hash.h:249
#define clib_bitmap_foreach(i, ai, body)
Macro to iterate across set bits in a bitmap.
Definition: bitmap.h:361
static void lpm_32_add(lpm_t *lpm, void *addr_v, u8 pfxlen, u32 value)
Definition: lpm.c:35
void clib_bihash_init(clib_bihash *h, char *name, u32 nbuckets, uword memory_size)
initialize a bounded index extensible hash table
u8 len
Definition: ip_types.api:49
static uint64_t masked_address64(uint64_t addr, uint8_t len)
Definition: lpm.c:29
#define clib_warning(format, args...)
Definition: error.h:59
static void lpm_128_delete(lpm_t *lpm, void *addr_v, u8 pfxlen)
Definition: lpm.c:139
signed int i32
Definition: types.h:77
#define hash_create(elts, value_bytes)
Definition: hash.h:696
#define ASSERT(truth)
int clib_bihash_search_inline_2(clib_bihash *h, clib_bihash_kv *search_key, clib_bihash_kv *valuep)
Search a bi-hash table.
void(* delete)(struct lpm_ *lpm, void *addr_v, u8 pfxlen)
Definition: lpm.h:26
static void * clib_mem_alloc(uword size)
Definition: mem.h:132
u64 uword
Definition: types.h:112
uword * hash[33]
Definition: lpm.h:30
static u32 lpm_32_lookup(lpm_t *lpm, void *addr_v, u8 pfxlen)
Definition: lpm.c:74
#define HASH_FLAG_NO_AUTO_SHRINK
Definition: hash.h:64
static u32 lpm_128_lookup(lpm_t *lpm, void *addr_v, u8 pfxlen)
Definition: lpm.c:109
u32 prefix_length_refcount[129]
Definition: lpm.h:35
uword * prefix_lengths_bitmap
Definition: lpm.h:34
static void lpm_32_delete(lpm_t *lpm, void *addr_v, u8 pfxlen)
Definition: lpm.c:60