lib/librte_table/rte_table_lpm.c

   1 /* SPDX-License-Identifier: BSD-3-Clause
   2  * Copyright(c) 2010-2014 Intel Corporation
   3  */
   4
   5 #include <string.h>
   6 #include <stdio.h>
   7
   8 #include <rte_common.h>
   9 #include <rte_mbuf.h>
  10 #include <rte_memory.h>
  11 #include <rte_malloc.h>
  12 #include <rte_byteorder.h>
  13 #include <rte_log.h>
  14 #include <rte_lpm.h>
  15
  16 #include "rte_table_lpm.h"
  17
  18 #ifndef RTE_TABLE_LPM_MAX_NEXT_HOPS
  19 #define RTE_TABLE_LPM_MAX_NEXT_HOPS                        65536
  20 #endif
  21
  22 #ifdef RTE_TABLE_STATS_COLLECT
  23
  24 #define RTE_TABLE_LPM_STATS_PKTS_IN_ADD(table, val) \
  25         table->stats.n_pkts_in += val
  26 #define RTE_TABLE_LPM_STATS_PKTS_LOOKUP_MISS(table, val) \
  27         table->stats.n_pkts_lookup_miss += val
  28
  29 #else
  30
  31 #define RTE_TABLE_LPM_STATS_PKTS_IN_ADD(table, val)
  32 #define RTE_TABLE_LPM_STATS_PKTS_LOOKUP_MISS(table, val)
  33
  34 #endif
  35
  36 struct rte_table_lpm {
  37         struct rte_table_stats stats;
  38
  39         /* Input parameters */
  40         uint32_t entry_size;
  41         uint32_t entry_unique_size;
  42         uint32_t n_rules;
  43         uint32_t offset;
  44
  45         /* Handle to low-level LPM table */
  46         struct rte_lpm *lpm;
  47
  48         /* Next Hop Table (NHT) */
  49         uint32_t nht_users[RTE_TABLE_LPM_MAX_NEXT_HOPS];
  50         uint8_t nht[0] __rte_cache_aligned;
  51 };
  52
  53 static void *
  54 rte_table_lpm_create(void *params, int socket_id, uint32_t entry_size)
  55 {
  56         struct rte_table_lpm_params *p = params;
  57         struct rte_table_lpm *lpm;
  58         struct rte_lpm_config lpm_config;
  59
  60         uint32_t total_size, nht_size;
  61
  62         /* Check input parameters */
  63         if (p == NULL) {
  64                 RTE_LOG(ERR, TABLE, "%s: NULL input parameters\n", __func__);
  65                 return NULL;
  66         }
  67         if (p->n_rules == 0) {
  68                 RTE_LOG(ERR, TABLE, "%s: Invalid n_rules\n", __func__);
  69                 return NULL;
  70         }
  71         if (p->number_tbl8s == 0) {
  72                 RTE_LOG(ERR, TABLE, "%s: Invalid number_tbl8s\n", __func__);
  73                 return NULL;
  74         }
  75         if (p->entry_unique_size == 0) {
  76                 RTE_LOG(ERR, TABLE, "%s: Invalid entry_unique_size\n",
  77                         __func__);
  78                 return NULL;
  79         }
  80         if (p->entry_unique_size > entry_size) {
  81                 RTE_LOG(ERR, TABLE, "%s: Invalid entry_unique_size\n",
  82                         __func__);
  83                 return NULL;
  84         }
  85         if (p->name == NULL) {
  86                 RTE_LOG(ERR, TABLE, "%s: Table name is NULL\n",
  87                         __func__);
  88                 return NULL;
  89         }
  90         entry_size = RTE_ALIGN(entry_size, sizeof(uint64_t));
  91
  92         /* Memory allocation */
  93         nht_size = RTE_TABLE_LPM_MAX_NEXT_HOPS * entry_size;
  94         total_size = sizeof(struct rte_table_lpm) + nht_size;
  95         lpm = rte_zmalloc_socket("TABLE", total_size, RTE_CACHE_LINE_SIZE,
  96                 socket_id);
  97         if (lpm == NULL) {
  98                 RTE_LOG(ERR, TABLE,
  99                         "%s: Cannot allocate %u bytes for LPM table\n",
 100                         __func__, total_size);
 101                 return NULL;
 102         }
 103
 104         /* LPM low-level table creation */
 105         lpm_config.max_rules = p->n_rules;
 106         lpm_config.number_tbl8s = p->number_tbl8s;
 107         lpm_config.flags = p->flags;
 108         lpm->lpm = rte_lpm_create(p->name, socket_id, &lpm_config);
 109
 110         if (lpm->lpm == NULL) {
 111                 rte_free(lpm);
 112                 RTE_LOG(ERR, TABLE, "Unable to create low-level LPM table\n");
 113                 return NULL;
 114         }
 115
 116         /* Memory initialization */
 117         lpm->entry_size = entry_size;
 118         lpm->entry_unique_size = p->entry_unique_size;
 119         lpm->n_rules = p->n_rules;
 120         lpm->offset = p->offset;
 121
 122         return lpm;
 123 }
 124
 125 static int
 126 rte_table_lpm_free(void *table)
 127 {
 128         struct rte_table_lpm *lpm = table;
 129
 130         /* Check input parameters */
 131         if (lpm == NULL) {
 132                 RTE_LOG(ERR, TABLE, "%s: table parameter is NULL\n", __func__);
 133                 return -EINVAL;
 134         }
 135
 136         /* Free previously allocated resources */
 137         rte_lpm_free(lpm->lpm);
 138         rte_free(lpm);
 139
 140         return 0;
 141 }
 142
 143 static int
 144 nht_find_free(struct rte_table_lpm *lpm, uint32_t *pos)
 145 {
 146         uint32_t i;
 147
 148         for (i = 0; i < RTE_TABLE_LPM_MAX_NEXT_HOPS; i++) {
 149                 if (lpm->nht_users[i] == 0) {
 150                         *pos = i;
 151                         return 1;
 152                 }
 153         }
 154
 155         return 0;
 156 }
 157
 158 static int
 159 nht_find_existing(struct rte_table_lpm *lpm, void *entry, uint32_t *pos)
 160 {
 161         uint32_t i;
 162
 163         for (i = 0; i < RTE_TABLE_LPM_MAX_NEXT_HOPS; i++) {
 164                 uint8_t *nht_entry = &lpm->nht[i * lpm->entry_size];
 165
 166                 if ((lpm->nht_users[i] > 0) && (memcmp(nht_entry, entry,
 167                         lpm->entry_unique_size) == 0)) {
 168                         *pos = i;
 169                         return 1;
 170                 }
 171         }
 172
 173         return 0;
 174 }
 175
 176 static int
 177 rte_table_lpm_entry_add(
 178         void *table,
 179         void *key,
 180         void *entry,
 181         int *key_found,
 182         void **entry_ptr)
 183 {
 184         struct rte_table_lpm *lpm = table;
 185         struct rte_table_lpm_key *ip_prefix = key;
 186         uint32_t nht_pos, nht_pos0_valid;
 187         int status;
 188         uint32_t nht_pos0 = 0;
 189
 190         /* Check input parameters */
 191         if (lpm == NULL) {
 192                 RTE_LOG(ERR, TABLE, "%s: table parameter is NULL\n", __func__);
 193                 return -EINVAL;
 194         }
 195         if (ip_prefix == NULL) {
 196                 RTE_LOG(ERR, TABLE, "%s: ip_prefix parameter is NULL\n",
 197                         __func__);
 198                 return -EINVAL;
 199         }
 200         if (entry == NULL) {
 201                 RTE_LOG(ERR, TABLE, "%s: entry parameter is NULL\n", __func__);
 202                 return -EINVAL;
 203         }
 204
 205         if ((ip_prefix->depth == 0) || (ip_prefix->depth > 32)) {
 206                 RTE_LOG(ERR, TABLE, "%s: invalid depth (%d)\n",
 207                         __func__, ip_prefix->depth);
 208                 return -EINVAL;
 209         }
 210
 211         /* Check if rule is already present in the table */
 212         status = rte_lpm_is_rule_present(lpm->lpm, ip_prefix->ip,
 213                 ip_prefix->depth, &nht_pos0);
 214         nht_pos0_valid = status > 0;
 215
 216         /* Find existing or free NHT entry */
 217         if (nht_find_existing(lpm, entry, &nht_pos) == 0) {
 218                 uint8_t *nht_entry;
 219
 220                 if (nht_find_free(lpm, &nht_pos) == 0) {
 221                         RTE_LOG(ERR, TABLE, "%s: NHT full\n", __func__);
 222                         return -1;
 223                 }
 224
 225                 nht_entry = &lpm->nht[nht_pos * lpm->entry_size];
 226                 memcpy(nht_entry, entry, lpm->entry_size);
 227         }
 228
 229         /* Add rule to low level LPM table */
 230         if (rte_lpm_add(lpm->lpm, ip_prefix->ip, ip_prefix->depth, nht_pos) < 0) {
 231                 RTE_LOG(ERR, TABLE, "%s: LPM rule add failed\n", __func__);
 232                 return -1;
 233         }
 234
 235         /* Commit NHT changes */
 236         lpm->nht_users[nht_pos]++;
 237         lpm->nht_users[nht_pos0] -= nht_pos0_valid;
 238
 239         *key_found = nht_pos0_valid;
 240         *entry_ptr = (void *) &lpm->nht[nht_pos * lpm->entry_size];
 241         return 0;
 242 }
 243
 244 static int
 245 rte_table_lpm_entry_delete(
 246         void *table,
 247         void *key,
 248         int *key_found,
 249         void *entry)
 250 {
 251         struct rte_table_lpm *lpm = table;
 252         struct rte_table_lpm_key *ip_prefix = key;
 253         uint32_t nht_pos;
 254         int status;
 255
 256         /* Check input parameters */
 257         if (lpm == NULL) {
 258                 RTE_LOG(ERR, TABLE, "%s: table parameter is NULL\n", __func__);
 259                 return -EINVAL;
 260         }
 261         if (ip_prefix == NULL) {
 262                 RTE_LOG(ERR, TABLE, "%s: ip_prefix parameter is NULL\n",
 263                         __func__);
 264                 return -EINVAL;
 265         }
 266         if ((ip_prefix->depth == 0) || (ip_prefix->depth > 32)) {
 267                 RTE_LOG(ERR, TABLE, "%s: invalid depth (%d)\n", __func__,
 268                         ip_prefix->depth);
 269                 return -EINVAL;
 270         }
 271
 272         /* Return if rule is not present in the table */
 273         status = rte_lpm_is_rule_present(lpm->lpm, ip_prefix->ip,
 274                 ip_prefix->depth, &nht_pos);
 275         if (status < 0) {
 276                 RTE_LOG(ERR, TABLE, "%s: LPM algorithmic error\n", __func__);
 277                 return -1;
 278         }
 279         if (status == 0) {
 280                 *key_found = 0;
 281                 return 0;
 282         }
 283
 284         /* Delete rule from the low-level LPM table */
 285         status = rte_lpm_delete(lpm->lpm, ip_prefix->ip, ip_prefix->depth);
 286         if (status) {
 287                 RTE_LOG(ERR, TABLE, "%s: LPM rule delete failed\n", __func__);
 288                 return -1;
 289         }
 290
 291         /* Commit NHT changes */
 292         lpm->nht_users[nht_pos]--;
 293
 294         *key_found = 1;
 295         if (entry)
 296                 memcpy(entry, &lpm->nht[nht_pos * lpm->entry_size],
 297                         lpm->entry_size);
 298
 299         return 0;
 300 }
 301
 302 static int
 303 rte_table_lpm_lookup(
 304         void *table,
 305         struct rte_mbuf **pkts,
 306         uint64_t pkts_mask,
 307         uint64_t *lookup_hit_mask,
 308         void **entries)
 309 {
 310         struct rte_table_lpm *lpm = (struct rte_table_lpm *) table;
 311         uint64_t pkts_out_mask = 0;
 312         uint32_t i;
 313
 314         __rte_unused uint32_t n_pkts_in = __builtin_popcountll(pkts_mask);
 315         RTE_TABLE_LPM_STATS_PKTS_IN_ADD(lpm, n_pkts_in);
 316
 317         pkts_out_mask = 0;
 318         for (i = 0; i < (uint32_t)(RTE_PORT_IN_BURST_SIZE_MAX -
 319                 __builtin_clzll(pkts_mask)); i++) {
 320                 uint64_t pkt_mask = 1LLU << i;
 321
 322                 if (pkt_mask & pkts_mask) {
 323                         struct rte_mbuf *pkt = pkts[i];
 324                         uint32_t ip = rte_bswap32(
 325                                 RTE_MBUF_METADATA_UINT32(pkt, lpm->offset));
 326                         int status;
 327                         uint32_t nht_pos;
 328
 329                         status = rte_lpm_lookup(lpm->lpm, ip, &nht_pos);
 330                         if (status == 0) {
 331                                 pkts_out_mask |= pkt_mask;
 332                                 entries[i] = (void *) &lpm->nht[nht_pos *
 333                                         lpm->entry_size];
 334                         }
 335                 }
 336         }
 337
 338         *lookup_hit_mask = pkts_out_mask;
 339         RTE_TABLE_LPM_STATS_PKTS_LOOKUP_MISS(lpm, n_pkts_in - __builtin_popcountll(pkts_out_mask));
 340         return 0;
 341 }
 342
 343 static int
 344 rte_table_lpm_stats_read(void *table, struct rte_table_stats *stats, int clear)
 345 {
 346         struct rte_table_lpm *t = table;
 347
 348         if (stats != NULL)
 349                 memcpy(stats, &t->stats, sizeof(t->stats));
 350
 351         if (clear)
 352                 memset(&t->stats, 0, sizeof(t->stats));
 353
 354         return 0;
 355 }
 356
 357 struct rte_table_ops rte_table_lpm_ops = {
 358         .f_create = rte_table_lpm_create,
 359         .f_free = rte_table_lpm_free,
 360         .f_add = rte_table_lpm_entry_add,
 361         .f_delete = rte_table_lpm_entry_delete,
 362         .f_add_bulk = NULL,
 363         .f_delete_bulk = NULL,
 364         .f_lookup = rte_table_lpm_lookup,
 365         .f_stats = rte_table_lpm_stats_read,
 366 };