1 /*- 2 * BSD LICENSE 3 * 4 * Copyright(c) 2010-2014 Intel Corporation. All rights reserved. 5 * All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 11 * * Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * * Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in 15 * the documentation and/or other materials provided with the 16 * distribution. 17 * * Neither the name of Intel Corporation nor the names of its 18 * contributors may be used to endorse or promote products derived 19 * from this software without specific prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 25 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 26 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 27 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 28 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 29 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 30 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 31 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 32 */ 33 34 #include <string.h> 35 #include <stdio.h> 36 37 #include <rte_common.h> 38 #include <rte_mbuf.h> 39 #include <rte_memory.h> 40 #include <rte_malloc.h> 41 #include <rte_byteorder.h> 42 #include <rte_log.h> 43 #include <rte_lpm6.h> 44 45 #include "rte_table_lpm_ipv6.h" 46 47 #define RTE_TABLE_LPM_MAX_NEXT_HOPS 256 48 49 #ifdef RTE_TABLE_STATS_COLLECT 50 51 #define RTE_TABLE_LPM_IPV6_STATS_PKTS_IN_ADD(table, val) \ 52 table->stats.n_pkts_in += val 53 #define RTE_TABLE_LPM_IPV6_STATS_PKTS_LOOKUP_MISS(table, val) \ 54 table->stats.n_pkts_lookup_miss += val 55 56 #else 57 58 #define RTE_TABLE_LPM_IPV6_STATS_PKTS_IN_ADD(table, val) 59 #define RTE_TABLE_LPM_IPV6_STATS_PKTS_LOOKUP_MISS(table, val) 60 61 #endif 62 63 struct rte_table_lpm_ipv6 { 64 struct rte_table_stats stats; 65 66 /* Input parameters */ 67 uint32_t entry_size; 68 uint32_t entry_unique_size; 69 uint32_t n_rules; 70 uint32_t offset; 71 72 /* Handle to low-level LPM table */ 73 struct rte_lpm6 *lpm; 74 75 /* Next Hop Table (NHT) */ 76 uint32_t nht_users[RTE_TABLE_LPM_MAX_NEXT_HOPS]; 77 uint8_t nht[0] __rte_cache_aligned; 78 }; 79 80 static void * 81 rte_table_lpm_ipv6_create(void *params, int socket_id, uint32_t entry_size) 82 { 83 struct rte_table_lpm_ipv6_params *p = 84 params; 85 struct rte_table_lpm_ipv6 *lpm; 86 struct rte_lpm6_config lpm6_config; 87 uint32_t total_size, nht_size; 88 89 /* Check input parameters */ 90 if (p == NULL) { 91 RTE_LOG(ERR, TABLE, "%s: NULL input parameters\n", __func__); 92 return NULL; 93 } 94 if (p->n_rules == 0) { 95 RTE_LOG(ERR, TABLE, "%s: Invalid n_rules\n", __func__); 96 return NULL; 97 } 98 if (p->number_tbl8s == 0) { 99 RTE_LOG(ERR, TABLE, "%s: Invalid n_rules\n", __func__); 100 return NULL; 101 } 102 if (p->entry_unique_size == 0) { 103 RTE_LOG(ERR, TABLE, "%s: Invalid entry_unique_size\n", 104 __func__); 105 return NULL; 106 } 107 if (p->entry_unique_size > entry_size) { 108 RTE_LOG(ERR, TABLE, "%s: Invalid entry_unique_size\n", 109 __func__); 110 return NULL; 111 } 112 if (p->name == NULL) { 113 RTE_LOG(ERR, TABLE, "%s: Table name is NULL\n", 114 __func__); 115 return NULL; 116 } 117 entry_size = RTE_ALIGN(entry_size, sizeof(uint64_t)); 118 119 /* Memory allocation */ 120 nht_size = RTE_TABLE_LPM_MAX_NEXT_HOPS * entry_size; 121 total_size = sizeof(struct rte_table_lpm_ipv6) + nht_size; 122 lpm = rte_zmalloc_socket("TABLE", total_size, RTE_CACHE_LINE_SIZE, 123 socket_id); 124 if (lpm == NULL) { 125 RTE_LOG(ERR, TABLE, 126 "%s: Cannot allocate %u bytes for LPM IPv6 table\n", 127 __func__, total_size); 128 return NULL; 129 } 130 131 /* LPM low-level table creation */ 132 lpm6_config.max_rules = p->n_rules; 133 lpm6_config.number_tbl8s = p->number_tbl8s; 134 lpm6_config.flags = 0; 135 lpm->lpm = rte_lpm6_create(p->name, socket_id, &lpm6_config); 136 if (lpm->lpm == NULL) { 137 rte_free(lpm); 138 RTE_LOG(ERR, TABLE, 139 "Unable to create low-level LPM IPv6 table\n"); 140 return NULL; 141 } 142 143 /* Memory initialization */ 144 lpm->entry_size = entry_size; 145 lpm->entry_unique_size = p->entry_unique_size; 146 lpm->n_rules = p->n_rules; 147 lpm->offset = p->offset; 148 149 return lpm; 150 } 151 152 static int 153 rte_table_lpm_ipv6_free(void *table) 154 { 155 struct rte_table_lpm_ipv6 *lpm = table; 156 157 /* Check input parameters */ 158 if (lpm == NULL) { 159 RTE_LOG(ERR, TABLE, "%s: table parameter is NULL\n", __func__); 160 return -EINVAL; 161 } 162 163 /* Free previously allocated resources */ 164 rte_lpm6_free(lpm->lpm); 165 rte_free(lpm); 166 167 return 0; 168 } 169 170 static int 171 nht_find_free(struct rte_table_lpm_ipv6 *lpm, uint32_t *pos) 172 { 173 uint32_t i; 174 175 for (i = 0; i < RTE_TABLE_LPM_MAX_NEXT_HOPS; i++) { 176 if (lpm->nht_users[i] == 0) { 177 *pos = i; 178 return 1; 179 } 180 } 181 182 return 0; 183 } 184 185 static int 186 nht_find_existing(struct rte_table_lpm_ipv6 *lpm, void *entry, uint32_t *pos) 187 { 188 uint32_t i; 189 190 for (i = 0; i < RTE_TABLE_LPM_MAX_NEXT_HOPS; i++) { 191 uint8_t *nht_entry = &lpm->nht[i * lpm->entry_size]; 192 193 if ((lpm->nht_users[i] > 0) && (memcmp(nht_entry, entry, 194 lpm->entry_unique_size) == 0)) { 195 *pos = i; 196 return 1; 197 } 198 } 199 200 return 0; 201 } 202 203 static int 204 rte_table_lpm_ipv6_entry_add( 205 void *table, 206 void *key, 207 void *entry, 208 int *key_found, 209 void **entry_ptr) 210 { 211 struct rte_table_lpm_ipv6 *lpm = table; 212 struct rte_table_lpm_ipv6_key *ip_prefix = 213 key; 214 uint32_t nht_pos, nht_pos0, nht_pos0_valid; 215 int status; 216 217 /* Check input parameters */ 218 if (lpm == NULL) { 219 RTE_LOG(ERR, TABLE, "%s: table parameter is NULL\n", __func__); 220 return -EINVAL; 221 } 222 if (ip_prefix == NULL) { 223 RTE_LOG(ERR, TABLE, "%s: ip_prefix parameter is NULL\n", 224 __func__); 225 return -EINVAL; 226 } 227 if (entry == NULL) { 228 RTE_LOG(ERR, TABLE, "%s: entry parameter is NULL\n", __func__); 229 return -EINVAL; 230 } 231 232 if ((ip_prefix->depth == 0) || (ip_prefix->depth > 128)) { 233 RTE_LOG(ERR, TABLE, "%s: invalid depth (%d)\n", __func__, 234 ip_prefix->depth); 235 return -EINVAL; 236 } 237 238 /* Check if rule is already present in the table */ 239 status = rte_lpm6_is_rule_present(lpm->lpm, ip_prefix->ip, 240 ip_prefix->depth, &nht_pos0); 241 nht_pos0_valid = status > 0; 242 243 /* Find existing or free NHT entry */ 244 if (nht_find_existing(lpm, entry, &nht_pos) == 0) { 245 uint8_t *nht_entry; 246 247 if (nht_find_free(lpm, &nht_pos) == 0) { 248 RTE_LOG(ERR, TABLE, "%s: NHT full\n", __func__); 249 return -1; 250 } 251 252 nht_entry = &lpm->nht[nht_pos * lpm->entry_size]; 253 memcpy(nht_entry, entry, lpm->entry_size); 254 } 255 256 /* Add rule to low level LPM table */ 257 if (rte_lpm6_add(lpm->lpm, ip_prefix->ip, ip_prefix->depth, 258 nht_pos) < 0) { 259 RTE_LOG(ERR, TABLE, "%s: LPM IPv6 rule add failed\n", __func__); 260 return -1; 261 } 262 263 /* Commit NHT changes */ 264 lpm->nht_users[nht_pos]++; 265 lpm->nht_users[nht_pos0] -= nht_pos0_valid; 266 267 *key_found = nht_pos0_valid; 268 *entry_ptr = (void *) &lpm->nht[nht_pos * lpm->entry_size]; 269 return 0; 270 } 271 272 static int 273 rte_table_lpm_ipv6_entry_delete( 274 void *table, 275 void *key, 276 int *key_found, 277 void *entry) 278 { 279 struct rte_table_lpm_ipv6 *lpm = table; 280 struct rte_table_lpm_ipv6_key *ip_prefix = 281 key; 282 uint32_t nht_pos; 283 int status; 284 285 /* Check input parameters */ 286 if (lpm == NULL) { 287 RTE_LOG(ERR, TABLE, "%s: table parameter is NULL\n", __func__); 288 return -EINVAL; 289 } 290 if (ip_prefix == NULL) { 291 RTE_LOG(ERR, TABLE, "%s: ip_prefix parameter is NULL\n", 292 __func__); 293 return -EINVAL; 294 } 295 if ((ip_prefix->depth == 0) || (ip_prefix->depth > 128)) { 296 RTE_LOG(ERR, TABLE, "%s: invalid depth (%d)\n", __func__, 297 ip_prefix->depth); 298 return -EINVAL; 299 } 300 301 /* Return if rule is not present in the table */ 302 status = rte_lpm6_is_rule_present(lpm->lpm, ip_prefix->ip, 303 ip_prefix->depth, &nht_pos); 304 if (status < 0) { 305 RTE_LOG(ERR, TABLE, "%s: LPM IPv6 algorithmic error\n", 306 __func__); 307 return -1; 308 } 309 if (status == 0) { 310 *key_found = 0; 311 return 0; 312 } 313 314 /* Delete rule from the low-level LPM table */ 315 status = rte_lpm6_delete(lpm->lpm, ip_prefix->ip, ip_prefix->depth); 316 if (status) { 317 RTE_LOG(ERR, TABLE, "%s: LPM IPv6 rule delete failed\n", 318 __func__); 319 return -1; 320 } 321 322 /* Commit NHT changes */ 323 lpm->nht_users[nht_pos]--; 324 325 *key_found = 1; 326 if (entry) 327 memcpy(entry, &lpm->nht[nht_pos * lpm->entry_size], 328 lpm->entry_size); 329 330 return 0; 331 } 332 333 static int 334 rte_table_lpm_ipv6_lookup( 335 void *table, 336 struct rte_mbuf **pkts, 337 uint64_t pkts_mask, 338 uint64_t *lookup_hit_mask, 339 void **entries) 340 { 341 struct rte_table_lpm_ipv6 *lpm = (struct rte_table_lpm_ipv6 *) table; 342 uint64_t pkts_out_mask = 0; 343 uint32_t i; 344 345 __rte_unused uint32_t n_pkts_in = __builtin_popcountll(pkts_mask); 346 RTE_TABLE_LPM_IPV6_STATS_PKTS_IN_ADD(lpm, n_pkts_in); 347 348 pkts_out_mask = 0; 349 for (i = 0; i < (uint32_t)(RTE_PORT_IN_BURST_SIZE_MAX - 350 __builtin_clzll(pkts_mask)); i++) { 351 uint64_t pkt_mask = 1LLU << i; 352 353 if (pkt_mask & pkts_mask) { 354 struct rte_mbuf *pkt = pkts[i]; 355 uint8_t *ip = RTE_MBUF_METADATA_UINT8_PTR(pkt, 356 lpm->offset); 357 int status; 358 uint32_t nht_pos; 359 360 status = rte_lpm6_lookup(lpm->lpm, ip, &nht_pos); 361 if (status == 0) { 362 pkts_out_mask |= pkt_mask; 363 entries[i] = (void *) &lpm->nht[nht_pos * 364 lpm->entry_size]; 365 } 366 } 367 } 368 369 *lookup_hit_mask = pkts_out_mask; 370 RTE_TABLE_LPM_IPV6_STATS_PKTS_LOOKUP_MISS(lpm, n_pkts_in - __builtin_popcountll(pkts_out_mask)); 371 return 0; 372 } 373 374 static int 375 rte_table_lpm_ipv6_stats_read(void *table, struct rte_table_stats *stats, int clear) 376 { 377 struct rte_table_lpm_ipv6 *t = table; 378 379 if (stats != NULL) 380 memcpy(stats, &t->stats, sizeof(t->stats)); 381 382 if (clear) 383 memset(&t->stats, 0, sizeof(t->stats)); 384 385 return 0; 386 } 387 388 struct rte_table_ops rte_table_lpm_ipv6_ops = { 389 .f_create = rte_table_lpm_ipv6_create, 390 .f_free = rte_table_lpm_ipv6_free, 391 .f_add = rte_table_lpm_ipv6_entry_add, 392 .f_delete = rte_table_lpm_ipv6_entry_delete, 393 .f_add_bulk = NULL, 394 .f_delete_bulk = NULL, 395 .f_lookup = rte_table_lpm_ipv6_lookup, 396 .f_stats = rte_table_lpm_ipv6_stats_read, 397 }; 398