@@ -6,9 +6,10 @@ include $(RTE_SDK)/mk/rte.vars.mk
# library name
LIB = librte_lpm.a
+CFLAGS += -DALLOW_EXPERIMENTAL_API
CFLAGS += -O3
CFLAGS += $(WERROR_FLAGS) -I$(SRCDIR)
-LDLIBS += -lrte_eal -lrte_hash
+LDLIBS += -lrte_eal -lrte_hash -lrte_rcu
EXPORT_MAP := rte_lpm_version.map
@@ -2,9 +2,11 @@
# Copyright(c) 2017 Intel Corporation
version = 2
+allow_experimental_apis = true
sources = files('rte_lpm.c', 'rte_lpm6.c')
headers = files('rte_lpm.h', 'rte_lpm6.h')
# since header files have different names, we can install all vector headers
# without worrying about which architecture we actually need
headers += files('rte_lpm_altivec.h', 'rte_lpm_neon.h', 'rte_lpm_sse.h')
deps += ['hash']
+deps += ['rcu']
@@ -1,5 +1,6 @@
/* SPDX-License-Identifier: BSD-3-Clause
* Copyright(c) 2010-2014 Intel Corporation
+ * Copyright(c) 2019 Arm Limited
*/
#include <string.h>
@@ -22,6 +23,7 @@
#include <rte_rwlock.h>
#include <rte_spinlock.h>
#include <rte_tailq.h>
+#include <rte_ring.h>
#include "rte_lpm.h"
@@ -39,6 +41,11 @@ enum valid_flag {
VALID
};
+struct __rte_lpm_qs_item {
+ uint64_t token; /**< QSBR token.*/
+ uint32_t index; /**< tbl8 group index.*/
+};
+
/* Macro to enable/disable run-time checks. */
#if defined(RTE_LIBRTE_LPM_DEBUG)
#include <rte_debug.h>
@@ -381,6 +388,8 @@ rte_lpm_free_v1604(struct rte_lpm *lpm)
rte_mcfg_tailq_write_unlock();
+ if (lpm->qsv)
+ rte_ring_free(lpm->qs_fifo);
rte_free(lpm->tbl8);
rte_free(lpm->rules_tbl);
rte_free(lpm);
@@ -390,6 +399,145 @@ BIND_DEFAULT_SYMBOL(rte_lpm_free, _v1604, 16.04);
MAP_STATIC_SYMBOL(void rte_lpm_free(struct rte_lpm *lpm),
rte_lpm_free_v1604);
+/* Add an item into FIFO.
+ * return: 0 - success
+ */
+static int
+__rte_lpm_rcu_qsbr_fifo_push(struct rte_ring *fifo,
+ struct __rte_lpm_qs_item *item)
+{
+ if (rte_ring_sp_enqueue(fifo, (void *)(uintptr_t)item->token) != 0) {
+ rte_errno = ENOSPC;
+ return 1;
+ }
+ if (rte_ring_sp_enqueue(fifo, (void *)(uintptr_t)item->index) != 0) {
+ void *obj;
+ /* token needs to be dequeued when index enqueue fails */
+ rte_ring_sc_dequeue(fifo, &obj);
+ rte_errno = ENOSPC;
+ return 1;
+ }
+
+ return 0;
+}
+
+/* Remove item from FIFO.
+ * Used when data observed by rte_ring_peek.
+ */
+static void
+__rte_lpm_rcu_qsbr_fifo_pop(struct rte_ring *fifo,
+ struct __rte_lpm_qs_item *item)
+{
+ void *obj_token = NULL;
+ void *obj_index = NULL;
+
+ (void)rte_ring_sc_dequeue(fifo, &obj_token);
+ (void)rte_ring_sc_dequeue(fifo, &obj_index);
+
+ if (item) {
+ item->token = (uint64_t)((uintptr_t)obj_token);
+ item->index = (uint32_t)((uintptr_t)obj_index);
+ }
+}
+
+/* Max number of tbl8 groups to reclaim at one time. */
+#define RCU_QSBR_RECLAIM_SIZE 8
+
+/* When RCU QSBR FIFO usage is above 1/(2^RCU_QSBR_RECLAIM_LEVEL),
+ * reclaim will be triggered by tbl8_free.
+ */
+#define RCU_QSBR_RECLAIM_LEVEL 3
+
+/* Reclaim some tbl8 groups based on quiescent state check.
+ * RCU_QSBR_RECLAIM_SIZE groups will be reclaimed at max.
+ * return: 0 - success, 1 - no group reclaimed.
+ */
+static uint32_t
+__rte_lpm_rcu_qsbr_reclaim_chunk(struct rte_lpm *lpm, uint32_t *index)
+{
+ struct __rte_lpm_qs_item qs_item;
+ struct rte_lpm_tbl_entry *tbl8_entry = NULL;
+ void *obj_token;
+ uint32_t cnt = 0;
+
+ /* Check reader threads quiescent state and
+ * reclaim as much tbl8 groups as possible.
+ */
+ while ((cnt < RCU_QSBR_RECLAIM_SIZE) &&
+ (rte_ring_peek(lpm->qs_fifo, &obj_token) == 0) &&
+ (rte_rcu_qsbr_check(lpm->qsv, (uint64_t)((uintptr_t)obj_token),
+ false) == 1)) {
+ __rte_lpm_rcu_qsbr_fifo_pop(lpm->qs_fifo, &qs_item);
+
+ tbl8_entry = &lpm->tbl8[qs_item.index *
+ RTE_LPM_TBL8_GROUP_NUM_ENTRIES];
+ memset(&tbl8_entry[0], 0,
+ RTE_LPM_TBL8_GROUP_NUM_ENTRIES *
+ sizeof(tbl8_entry[0]));
+ cnt++;
+ }
+
+ if (cnt) {
+ if (index)
+ *index = qs_item.index;
+ return 0;
+ }
+ return 1;
+}
+
+/* Trigger tbl8 group reclaim when necessary.
+ * Reclaim happens when RCU QSBR queue usage is over 12.5%.
+ */
+static void
+__rte_lpm_rcu_qsbr_try_reclaim(struct rte_lpm *lpm)
+{
+ if (lpm->qsv == NULL)
+ return;
+
+ if (rte_ring_count(lpm->qs_fifo) <
+ (rte_ring_get_capacity(lpm->qs_fifo) >> RCU_QSBR_RECLAIM_LEVEL))
+ return;
+
+ (void)__rte_lpm_rcu_qsbr_reclaim_chunk(lpm, NULL);
+}
+
+/* Associate QSBR variable with an LPM object.
+ */
+int
+rte_lpm_rcu_qsbr_add(struct rte_lpm *lpm, struct rte_rcu_qsbr *v)
+{
+ uint32_t qs_fifo_size;
+ char rcu_ring_name[RTE_RING_NAMESIZE];
+
+ if ((lpm == NULL) || (v == NULL)) {
+ rte_errno = EINVAL;
+ return 1;
+ }
+
+ if (lpm->qsv) {
+ rte_errno = EEXIST;
+ return 1;
+ }
+
+ /* round up qs_fifo_size to next power of two that is not less than
+ * number_tbl8s. Will store 'token' and 'index'.
+ */
+ qs_fifo_size = 2 * rte_align32pow2(lpm->number_tbl8s);
+
+ /* Init QSBR reclaiming FIFO. */
+ snprintf(rcu_ring_name, sizeof(rcu_ring_name), "LPM_RCU_%s", lpm->name);
+ lpm->qs_fifo = rte_ring_create(rcu_ring_name, qs_fifo_size,
+ SOCKET_ID_ANY, 0);
+ if (lpm->qs_fifo == NULL) {
+ RTE_LOG(ERR, LPM, "LPM QS FIFO memory allocation failed\n");
+ rte_errno = ENOMEM;
+ return 1;
+ }
+ lpm->qsv = v;
+
+ return 0;
+}
+
/*
* Adds a rule to the rule table.
*
@@ -640,6 +788,35 @@ rule_find_v1604(struct rte_lpm *lpm, uint32_t ip_masked, uint8_t depth)
return -EINVAL;
}
+static int32_t
+tbl8_alloc_reclaimed(struct rte_lpm *lpm)
+{
+ struct rte_lpm_tbl_entry *tbl8_entry = NULL;
+ uint32_t index;
+
+ if (lpm->qsv != NULL) {
+ if (__rte_lpm_rcu_qsbr_reclaim_chunk(lpm, &index) == 0) {
+ /* Set the last reclaimed tbl8 group as VALID. */
+ struct rte_lpm_tbl_entry new_tbl8_entry = {
+ .next_hop = 0,
+ .valid = INVALID,
+ .depth = 0,
+ .valid_group = VALID,
+ };
+
+ tbl8_entry = &lpm->tbl8[index *
+ RTE_LPM_TBL8_GROUP_NUM_ENTRIES];
+ __atomic_store(tbl8_entry, &new_tbl8_entry,
+ __ATOMIC_RELAXED);
+
+ /* Return group index for reclaimed tbl8 group. */
+ return index;
+ }
+ }
+
+ return -ENOSPC;
+}
+
/*
* Find, clean and allocate a tbl8.
*/
@@ -679,14 +856,15 @@ tbl8_alloc_v20(struct rte_lpm_tbl_entry_v20 *tbl8)
}
static int32_t
-tbl8_alloc_v1604(struct rte_lpm_tbl_entry *tbl8, uint32_t number_tbl8s)
+tbl8_alloc_v1604(struct rte_lpm *lpm)
{
uint32_t group_idx; /* tbl8 group index. */
struct rte_lpm_tbl_entry *tbl8_entry;
/* Scan through tbl8 to find a free (i.e. INVALID) tbl8 group. */
- for (group_idx = 0; group_idx < number_tbl8s; group_idx++) {
- tbl8_entry = &tbl8[group_idx * RTE_LPM_TBL8_GROUP_NUM_ENTRIES];
+ for (group_idx = 0; group_idx < lpm->number_tbl8s; group_idx++) {
+ tbl8_entry = &lpm->tbl8[group_idx *
+ RTE_LPM_TBL8_GROUP_NUM_ENTRIES];
/* If a free tbl8 group is found clean it and set as VALID. */
if (!tbl8_entry->valid_group) {
struct rte_lpm_tbl_entry new_tbl8_entry = {
@@ -708,8 +886,8 @@ tbl8_alloc_v1604(struct rte_lpm_tbl_entry *tbl8, uint32_t number_tbl8s)
}
}
- /* If there are no tbl8 groups free then return error. */
- return -ENOSPC;
+ /* If there are no tbl8 groups free then check reclaim queue. */
+ return tbl8_alloc_reclaimed(lpm);
}
static void
@@ -728,13 +906,27 @@ tbl8_free_v20(struct rte_lpm_tbl_entry_v20 *tbl8, uint32_t tbl8_group_start)
}
static void
-tbl8_free_v1604(struct rte_lpm_tbl_entry *tbl8, uint32_t tbl8_group_start)
+tbl8_free_v1604(struct rte_lpm *lpm, uint32_t tbl8_group_start)
{
- /* Set tbl8 group invalid*/
+ struct __rte_lpm_qs_item qs_item;
struct rte_lpm_tbl_entry zero_tbl8_entry = {0};
- __atomic_store(&tbl8[tbl8_group_start], &zero_tbl8_entry,
- __ATOMIC_RELAXED);
+ if (lpm->qsv != NULL) {
+ /* Push into QSBR FIFO. */
+ qs_item.token = rte_rcu_qsbr_start(lpm->qsv);
+ qs_item.index = tbl8_group_start;
+ if (__rte_lpm_rcu_qsbr_fifo_push(lpm->qs_fifo, &qs_item) != 0)
+ RTE_LOG(ERR, LPM, "Failed to push QSBR FIFO\n");
+
+ /* Speculatively reclaim tbl8 groups.
+ * Help spread the reclaim work load across multiple calls.
+ */
+ __rte_lpm_rcu_qsbr_try_reclaim(lpm);
+ } else {
+ /* Set tbl8 group invalid*/
+ __atomic_store(&lpm->tbl8[tbl8_group_start], &zero_tbl8_entry,
+ __ATOMIC_RELAXED);
+ }
}
static __rte_noinline int32_t
@@ -1037,7 +1229,7 @@ add_depth_big_v1604(struct rte_lpm *lpm, uint32_t ip_masked, uint8_t depth,
if (!lpm->tbl24[tbl24_index].valid) {
/* Search for a free tbl8 group. */
- tbl8_group_index = tbl8_alloc_v1604(lpm->tbl8, lpm->number_tbl8s);
+ tbl8_group_index = tbl8_alloc_v1604(lpm);
/* Check tbl8 allocation was successful. */
if (tbl8_group_index < 0) {
@@ -1083,7 +1275,7 @@ add_depth_big_v1604(struct rte_lpm *lpm, uint32_t ip_masked, uint8_t depth,
} /* If valid entry but not extended calculate the index into Table8. */
else if (lpm->tbl24[tbl24_index].valid_group == 0) {
/* Search for free tbl8 group. */
- tbl8_group_index = tbl8_alloc_v1604(lpm->tbl8, lpm->number_tbl8s);
+ tbl8_group_index = tbl8_alloc_v1604(lpm);
if (tbl8_group_index < 0) {
return tbl8_group_index;
@@ -1818,7 +2010,7 @@ delete_depth_big_v1604(struct rte_lpm *lpm, uint32_t ip_masked,
*/
lpm->tbl24[tbl24_index].valid = 0;
__atomic_thread_fence(__ATOMIC_RELEASE);
- tbl8_free_v1604(lpm->tbl8, tbl8_group_start);
+ tbl8_free_v1604(lpm, tbl8_group_start);
} else if (tbl8_recycle_index > -1) {
/* Update tbl24 entry. */
struct rte_lpm_tbl_entry new_tbl24_entry = {
@@ -1834,7 +2026,7 @@ delete_depth_big_v1604(struct rte_lpm *lpm, uint32_t ip_masked,
__atomic_store(&lpm->tbl24[tbl24_index], &new_tbl24_entry,
__ATOMIC_RELAXED);
__atomic_thread_fence(__ATOMIC_RELEASE);
- tbl8_free_v1604(lpm->tbl8, tbl8_group_start);
+ tbl8_free_v1604(lpm, tbl8_group_start);
}
#undef group_idx
return 0;
@@ -1,5 +1,6 @@
/* SPDX-License-Identifier: BSD-3-Clause
* Copyright(c) 2010-2014 Intel Corporation
+ * Copyright(c) 2019 Arm Limited
*/
#ifndef _RTE_LPM_H_
@@ -21,6 +22,7 @@
#include <rte_common.h>
#include <rte_vect.h>
#include <rte_compat.h>
+#include <rte_rcu_qsbr.h>
#ifdef __cplusplus
extern "C" {
@@ -186,6 +188,8 @@ struct rte_lpm {
__rte_cache_aligned; /**< LPM tbl24 table. */
struct rte_lpm_tbl_entry *tbl8; /**< LPM tbl8 table. */
struct rte_lpm_rule *rules_tbl; /**< LPM rules. */
+ struct rte_rcu_qsbr *qsv; /**< RCU QSBR variable for tbl8 group.*/
+ struct rte_ring *qs_fifo; /**< RCU QSBR reclaiming queue. */
};
/**
@@ -248,6 +252,24 @@ rte_lpm_free_v20(struct rte_lpm_v20 *lpm);
void
rte_lpm_free_v1604(struct rte_lpm *lpm);
+/**
+ * Associate RCU QSBR variable with an LPM object.
+ *
+ * @param lpm
+ * the lpm object to add RCU QSBR
+ * @param v
+ * RCU QSBR variable
+ * @return
+ * On success - 0
+ * On error - 1 with error code set in rte_errno.
+ * Possible rte_errno codes are:
+ * - EINVAL - invalid pointer
+ * - EEXIST - already added QSBR
+ * - ENOMEM - memory allocation failure
+ */
+__rte_experimental
+int rte_lpm_rcu_qsbr_add(struct rte_lpm *lpm, struct rte_rcu_qsbr *v);
+
/**
* Add a rule to the LPM table.
*
@@ -44,3 +44,9 @@ DPDK_17.05 {
rte_lpm6_lookup_bulk_func;
} DPDK_16.04;
+
+EXPERIMENTAL {
+ global:
+
+ rte_lpm_rcu_qsbr_add;
+};
@@ -11,6 +11,7 @@
libraries = [
'kvargs', # eal depends on kvargs
'eal', # everything depends on eal
+ 'rcu', # hash and lpm depends on this
'ring', 'mempool', 'mbuf', 'net', 'meter', 'ethdev', 'pci', # core
'cmdline',
'metrics', # bitrate/latency stats depends on this
@@ -22,7 +23,7 @@ libraries = [
'gro', 'gso', 'ip_frag', 'jobstats',
'kni', 'latencystats', 'lpm', 'member',
'power', 'pdump', 'rawdev',
- 'rcu', 'reorder', 'sched', 'security', 'stack', 'vhost',
+ 'reorder', 'sched', 'security', 'stack', 'vhost',
# ipsec lib depends on net, crypto and security
'ipsec',
# add pkt framework libs which use other libs from above