LCOV - code coverage report
Current view: top level - lib/table - rte_table_lpm.c (source / functions) Hit Total Coverage
Test: Code coverage Lines: 105 130 80.8 %
Date: 2024-01-22 15:35:40 Functions: 6 7 85.7 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 49 66 74.2 %

           Branch data     Line data    Source code
       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_malloc.h>
      10                 :            : #include <rte_byteorder.h>
      11                 :            : #include <rte_log.h>
      12                 :            : #include <rte_lpm.h>
      13                 :            : 
      14                 :            : #include "rte_table_lpm.h"
      15                 :            : 
      16                 :            : #include "table_log.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                 :         11 : 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         [ +  + ]:         11 :         if (p == NULL) {
      64                 :          1 :                 TABLE_LOG(ERR, "%s: NULL input parameters", __func__);
      65                 :          1 :                 return NULL;
      66                 :            :         }
      67         [ +  + ]:         10 :         if (p->n_rules == 0) {
      68                 :          2 :                 TABLE_LOG(ERR, "%s: Invalid n_rules", __func__);
      69                 :          2 :                 return NULL;
      70                 :            :         }
      71         [ -  + ]:          8 :         if (p->number_tbl8s == 0) {
      72                 :          0 :                 TABLE_LOG(ERR, "%s: Invalid number_tbl8s", __func__);
      73                 :          0 :                 return NULL;
      74                 :            :         }
      75         [ +  + ]:          8 :         if (p->entry_unique_size == 0) {
      76                 :          1 :                 TABLE_LOG(ERR, "%s: Invalid entry_unique_size",
      77                 :            :                         __func__);
      78                 :          1 :                 return NULL;
      79                 :            :         }
      80         [ +  + ]:          7 :         if (p->entry_unique_size > entry_size) {
      81                 :          1 :                 TABLE_LOG(ERR, "%s: Invalid entry_unique_size",
      82                 :            :                         __func__);
      83                 :          1 :                 return NULL;
      84                 :            :         }
      85         [ +  + ]:          6 :         if (p->name == NULL) {
      86                 :          1 :                 TABLE_LOG(ERR, "%s: Table name is NULL",
      87                 :            :                         __func__);
      88                 :          1 :                 return NULL;
      89                 :            :         }
      90                 :          5 :         entry_size = RTE_ALIGN(entry_size, sizeof(uint64_t));
      91                 :            : 
      92                 :            :         /* Memory allocation */
      93                 :          5 :         nht_size = RTE_TABLE_LPM_MAX_NEXT_HOPS * entry_size;
      94                 :          5 :         total_size = sizeof(struct rte_table_lpm) + nht_size;
      95                 :          5 :         lpm = rte_zmalloc_socket("TABLE", total_size, RTE_CACHE_LINE_SIZE,
      96                 :            :                 socket_id);
      97         [ -  + ]:          5 :         if (lpm == NULL) {
      98                 :          0 :                 TABLE_LOG(ERR,
      99                 :            :                         "%s: Cannot allocate %u bytes for LPM table",
     100                 :            :                         __func__, total_size);
     101                 :          0 :                 return NULL;
     102                 :            :         }
     103                 :            : 
     104                 :            :         /* LPM low-level table creation */
     105                 :          5 :         lpm_config.max_rules = p->n_rules;
     106                 :          5 :         lpm_config.number_tbl8s = p->number_tbl8s;
     107                 :          5 :         lpm_config.flags = p->flags;
     108                 :          5 :         lpm->lpm = rte_lpm_create(p->name, socket_id, &lpm_config);
     109                 :            : 
     110         [ -  + ]:          5 :         if (lpm->lpm == NULL) {
     111                 :          0 :                 rte_free(lpm);
     112                 :          0 :                 TABLE_LOG(ERR, "Unable to create low-level LPM table");
     113                 :          0 :                 return NULL;
     114                 :            :         }
     115                 :            : 
     116                 :            :         /* Memory initialization */
     117                 :          5 :         lpm->entry_size = entry_size;
     118                 :          5 :         lpm->entry_unique_size = p->entry_unique_size;
     119                 :          5 :         lpm->n_rules = p->n_rules;
     120                 :          5 :         lpm->offset = p->offset;
     121                 :            : 
     122                 :          5 :         return lpm;
     123                 :            : }
     124                 :            : 
     125                 :            : static int
     126                 :          6 : rte_table_lpm_free(void *table)
     127                 :            : {
     128                 :            :         struct rte_table_lpm *lpm = table;
     129                 :            : 
     130                 :            :         /* Check input parameters */
     131         [ +  + ]:          6 :         if (lpm == NULL) {
     132                 :          1 :                 TABLE_LOG(ERR, "%s: table parameter is NULL", __func__);
     133                 :          1 :                 return -EINVAL;
     134                 :            :         }
     135                 :            : 
     136                 :            :         /* Free previously allocated resources */
     137                 :          5 :         rte_lpm_free(lpm->lpm);
     138                 :          5 :         rte_free(lpm);
     139                 :            : 
     140                 :          5 :         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         [ +  - ]:          5 :         for (i = 0; i < RTE_TABLE_LPM_MAX_NEXT_HOPS; i++) {
     149         [ +  + ]:          5 :                 if (lpm->nht_users[i] == 0) {
     150                 :          4 :                         *pos = i;
     151                 :            :                         return 1;
     152                 :            :                 }
     153                 :            :         }
     154                 :            : 
     155                 :            :         return 0;
     156                 :            : }
     157                 :            : 
     158                 :            : static int
     159                 :          4 : nht_find_existing(struct rte_table_lpm *lpm, void *entry, uint32_t *pos)
     160                 :            : {
     161                 :            :         uint32_t i;
     162                 :            : 
     163         [ +  + ]:     262148 :         for (i = 0; i < RTE_TABLE_LPM_MAX_NEXT_HOPS; i++) {
     164                 :     262144 :                 uint8_t *nht_entry = &lpm->nht[i * lpm->entry_size];
     165                 :            : 
     166         [ +  + ]:     262144 :                 if ((lpm->nht_users[i] > 0) && (memcmp(nht_entry, entry,
     167         [ -  + ]:          1 :                         lpm->entry_unique_size) == 0)) {
     168                 :          0 :                         *pos = i;
     169                 :          0 :                         return 1;
     170                 :            :                 }
     171                 :            :         }
     172                 :            : 
     173                 :            :         return 0;
     174                 :            : }
     175                 :            : 
     176                 :            : static int
     177                 :         11 : 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                 :         11 :         uint32_t nht_pos0 = 0;
     189                 :            : 
     190                 :            :         /* Check input parameters */
     191         [ +  + ]:         11 :         if (lpm == NULL) {
     192                 :          1 :                 TABLE_LOG(ERR, "%s: table parameter is NULL", __func__);
     193                 :          1 :                 return -EINVAL;
     194                 :            :         }
     195         [ +  + ]:         10 :         if (ip_prefix == NULL) {
     196                 :          1 :                 TABLE_LOG(ERR, "%s: ip_prefix parameter is NULL",
     197                 :            :                         __func__);
     198                 :          1 :                 return -EINVAL;
     199                 :            :         }
     200         [ +  + ]:          9 :         if (entry == NULL) {
     201                 :          1 :                 TABLE_LOG(ERR, "%s: entry parameter is NULL", __func__);
     202                 :          1 :                 return -EINVAL;
     203                 :            :         }
     204                 :            : 
     205         [ +  + ]:          8 :         if ((ip_prefix->depth == 0) || (ip_prefix->depth > 32)) {
     206                 :          4 :                 TABLE_LOG(ERR, "%s: invalid depth (%d)",
     207                 :            :                         __func__, ip_prefix->depth);
     208                 :          4 :                 return -EINVAL;
     209                 :            :         }
     210                 :            : 
     211                 :            :         /* Check if rule is already present in the table */
     212                 :          4 :         status = rte_lpm_is_rule_present(lpm->lpm, ip_prefix->ip,
     213                 :            :                 ip_prefix->depth, &nht_pos0);
     214                 :          4 :         nht_pos0_valid = status > 0;
     215                 :            : 
     216                 :            :         /* Find existing or free NHT entry */
     217         [ +  - ]:          4 :         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                 :          0 :                         TABLE_LOG(ERR, "%s: NHT full", __func__);
     222                 :          0 :                         return -1;
     223                 :            :                 }
     224                 :            : 
     225                 :          4 :                 nht_entry = &lpm->nht[nht_pos * lpm->entry_size];
     226                 :          4 :                 memcpy(nht_entry, entry, lpm->entry_size);
     227                 :            :         }
     228                 :            : 
     229                 :            :         /* Add rule to low level LPM table */
     230         [ -  + ]:          4 :         if (rte_lpm_add(lpm->lpm, ip_prefix->ip, ip_prefix->depth, nht_pos) < 0) {
     231                 :          0 :                 TABLE_LOG(ERR, "%s: LPM rule add failed", __func__);
     232                 :          0 :                 return -1;
     233                 :            :         }
     234                 :            : 
     235                 :            :         /* Commit NHT changes */
     236                 :          4 :         lpm->nht_users[nht_pos]++;
     237                 :          4 :         lpm->nht_users[nht_pos0] -= nht_pos0_valid;
     238                 :            : 
     239                 :          4 :         *key_found = nht_pos0_valid;
     240                 :          4 :         *entry_ptr = (void *) &lpm->nht[nht_pos * lpm->entry_size];
     241                 :          4 :         return 0;
     242                 :            : }
     243                 :            : 
     244                 :            : static int
     245                 :          7 : 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         [ +  + ]:          7 :         if (lpm == NULL) {
     258                 :          1 :                 TABLE_LOG(ERR, "%s: table parameter is NULL", __func__);
     259                 :          1 :                 return -EINVAL;
     260                 :            :         }
     261         [ +  + ]:          6 :         if (ip_prefix == NULL) {
     262                 :          1 :                 TABLE_LOG(ERR, "%s: ip_prefix parameter is NULL",
     263                 :            :                         __func__);
     264                 :          1 :                 return -EINVAL;
     265                 :            :         }
     266         [ +  + ]:          5 :         if ((ip_prefix->depth == 0) || (ip_prefix->depth > 32)) {
     267                 :          2 :                 TABLE_LOG(ERR, "%s: invalid depth (%d)", __func__,
     268                 :            :                         ip_prefix->depth);
     269                 :          2 :                 return -EINVAL;
     270                 :            :         }
     271                 :            : 
     272                 :            :         /* Return if rule is not present in the table */
     273                 :          3 :         status = rte_lpm_is_rule_present(lpm->lpm, ip_prefix->ip,
     274                 :            :                 ip_prefix->depth, &nht_pos);
     275         [ -  + ]:          3 :         if (status < 0) {
     276                 :          0 :                 TABLE_LOG(ERR, "%s: LPM algorithmic error", __func__);
     277                 :          0 :                 return -1;
     278                 :            :         }
     279         [ +  + ]:          3 :         if (status == 0) {
     280                 :          1 :                 *key_found = 0;
     281                 :          1 :                 return 0;
     282                 :            :         }
     283                 :            : 
     284                 :            :         /* Delete rule from the low-level LPM table */
     285                 :          2 :         status = rte_lpm_delete(lpm->lpm, ip_prefix->ip, ip_prefix->depth);
     286         [ -  + ]:          2 :         if (status) {
     287                 :          0 :                 TABLE_LOG(ERR, "%s: LPM rule delete failed", __func__);
     288                 :          0 :                 return -1;
     289                 :            :         }
     290                 :            : 
     291                 :            :         /* Commit NHT changes */
     292                 :          2 :         lpm->nht_users[nht_pos]--;
     293                 :            : 
     294                 :          2 :         *key_found = 1;
     295         [ -  + ]:          2 :         if (entry)
     296                 :          0 :                 memcpy(entry, &lpm->nht[nht_pos * lpm->entry_size],
     297                 :          0 :                         lpm->entry_size);
     298                 :            : 
     299                 :            :         return 0;
     300                 :            : }
     301                 :            : 
     302                 :            : static int
     303                 :          7 : 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 = rte_popcount64(pkts_mask);
     315                 :            :         RTE_TABLE_LPM_STATS_PKTS_IN_ADD(lpm, n_pkts_in);
     316                 :            : 
     317                 :            :         pkts_out_mask = 0;
     318         [ +  + ]:        273 :         for (i = 0; i < (uint32_t)(RTE_PORT_IN_BURST_SIZE_MAX -
     319                 :        266 :                 rte_clz64(pkts_mask)); i++) {
     320                 :        266 :                 uint64_t pkt_mask = 1LLU << i;
     321                 :            : 
     322         [ +  - ]:        266 :                 if (pkt_mask & pkts_mask) {
     323                 :        266 :                         struct rte_mbuf *pkt = pkts[i];
     324         [ -  + ]:        266 :                         uint32_t ip = rte_bswap32(
     325                 :            :                                 RTE_MBUF_METADATA_UINT32(pkt, lpm->offset));
     326                 :            :                         int status;
     327                 :            :                         uint32_t nht_pos;
     328                 :            : 
     329         [ -  + ]:        266 :                         status = rte_lpm_lookup(lpm->lpm, ip, &nht_pos);
     330                 :            :                         if (status == 0) {
     331                 :        158 :                                 pkts_out_mask |= pkt_mask;
     332                 :        158 :                                 entries[i] = (void *) &lpm->nht[nht_pos *
     333                 :        158 :                                         lpm->entry_size];
     334                 :            :                         }
     335                 :            :                 }
     336                 :            :         }
     337                 :            : 
     338                 :          7 :         *lookup_hit_mask = pkts_out_mask;
     339                 :            :         RTE_TABLE_LPM_STATS_PKTS_LOOKUP_MISS(lpm, n_pkts_in - rte_popcount64(pkts_out_mask));
     340                 :          7 :         return 0;
     341                 :            : }
     342                 :            : 
     343                 :            : static int
     344                 :          0 : rte_table_lpm_stats_read(void *table, struct rte_table_stats *stats, int clear)
     345                 :            : {
     346                 :            :         struct rte_table_lpm *t = table;
     347                 :            : 
     348         [ #  # ]:          0 :         if (stats != NULL)
     349                 :          0 :                 memcpy(stats, &t->stats, sizeof(t->stats));
     350                 :            : 
     351         [ #  # ]:          0 :         if (clear)
     352                 :          0 :                 memset(&t->stats, 0, sizeof(t->stats));
     353                 :            : 
     354                 :          0 :         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                 :            : };

Generated by: LCOV version 1.14