1 /* SPDX-License-Identifier: BSD-3-Clause
3 * Copyright (c) 2018-2020 Arm Limited
12 #include <rte_common.h>
14 #include <rte_memory.h>
15 #include <rte_malloc.h>
17 #include <rte_atomic.h>
18 #include <rte_per_lcore.h>
19 #include <rte_lcore.h>
20 #include <rte_errno.h>
21 #include <rte_ring_elem.h>
23 #include "rte_rcu_qsbr.h"
24 #include "rcu_qsbr_pvt.h"
26 /* Get the memory size of QSBR variable */
28 rte_rcu_qsbr_get_memsize(uint32_t max_threads)
32 if (max_threads == 0) {
33 rte_log(RTE_LOG_ERR, rte_rcu_log_type,
34 "%s(): Invalid max_threads %u\n",
35 __func__, max_threads);
41 sz = sizeof(struct rte_rcu_qsbr);
43 /* Add the size of quiescent state counter array */
44 sz += sizeof(struct rte_rcu_qsbr_cnt) * max_threads;
46 /* Add the size of the registered thread ID bitmap array */
47 sz += __RTE_QSBR_THRID_ARRAY_SIZE(max_threads);
52 /* Initialize a quiescent state variable */
54 rte_rcu_qsbr_init(struct rte_rcu_qsbr *v, uint32_t max_threads)
59 rte_log(RTE_LOG_ERR, rte_rcu_log_type,
60 "%s(): Invalid input parameter\n", __func__);
66 sz = rte_rcu_qsbr_get_memsize(max_threads);
70 /* Set all the threads to offline */
72 v->max_threads = max_threads;
73 v->num_elems = RTE_ALIGN_MUL_CEIL(max_threads,
74 __RTE_QSBR_THRID_ARRAY_ELM_SIZE) /
75 __RTE_QSBR_THRID_ARRAY_ELM_SIZE;
76 v->token = __RTE_QSBR_CNT_INIT;
77 v->acked_token = __RTE_QSBR_CNT_INIT - 1;
82 /* Register a reader thread to report its quiescent state
86 rte_rcu_qsbr_thread_register(struct rte_rcu_qsbr *v, unsigned int thread_id)
88 unsigned int i, id, success;
89 uint64_t old_bmap, new_bmap;
91 if (v == NULL || thread_id >= v->max_threads) {
92 rte_log(RTE_LOG_ERR, rte_rcu_log_type,
93 "%s(): Invalid input parameter\n", __func__);
99 __RTE_RCU_IS_LOCK_CNT_ZERO(v, thread_id, ERR, "Lock counter %u\n",
100 v->qsbr_cnt[thread_id].lock_cnt);
102 id = thread_id & __RTE_QSBR_THRID_MASK;
103 i = thread_id >> __RTE_QSBR_THRID_INDEX_SHIFT;
105 /* Make sure that the counter for registered threads does not
106 * go out of sync. Hence, additional checks are required.
108 /* Check if the thread is already registered */
109 old_bmap = __atomic_load_n(__RTE_QSBR_THRID_ARRAY_ELM(v, i),
111 if (old_bmap & 1UL << id)
115 new_bmap = old_bmap | (1UL << id);
116 success = __atomic_compare_exchange(
117 __RTE_QSBR_THRID_ARRAY_ELM(v, i),
118 &old_bmap, &new_bmap, 0,
119 __ATOMIC_RELEASE, __ATOMIC_RELAXED);
122 __atomic_fetch_add(&v->num_threads,
123 1, __ATOMIC_RELAXED);
124 else if (old_bmap & (1UL << id))
125 /* Someone else registered this thread.
126 * Counter should not be incremented.
129 } while (success == 0);
134 /* Remove a reader thread, from the list of threads reporting their
135 * quiescent state on a QS variable.
138 rte_rcu_qsbr_thread_unregister(struct rte_rcu_qsbr *v, unsigned int thread_id)
140 unsigned int i, id, success;
141 uint64_t old_bmap, new_bmap;
143 if (v == NULL || thread_id >= v->max_threads) {
144 rte_log(RTE_LOG_ERR, rte_rcu_log_type,
145 "%s(): Invalid input parameter\n", __func__);
151 __RTE_RCU_IS_LOCK_CNT_ZERO(v, thread_id, ERR, "Lock counter %u\n",
152 v->qsbr_cnt[thread_id].lock_cnt);
154 id = thread_id & __RTE_QSBR_THRID_MASK;
155 i = thread_id >> __RTE_QSBR_THRID_INDEX_SHIFT;
157 /* Make sure that the counter for registered threads does not
158 * go out of sync. Hence, additional checks are required.
160 /* Check if the thread is already unregistered */
161 old_bmap = __atomic_load_n(__RTE_QSBR_THRID_ARRAY_ELM(v, i),
163 if (!(old_bmap & (1UL << id)))
167 new_bmap = old_bmap & ~(1UL << id);
168 /* Make sure any loads of the shared data structure are
169 * completed before removal of the thread from the list of
172 success = __atomic_compare_exchange(
173 __RTE_QSBR_THRID_ARRAY_ELM(v, i),
174 &old_bmap, &new_bmap, 0,
175 __ATOMIC_RELEASE, __ATOMIC_RELAXED);
178 __atomic_fetch_sub(&v->num_threads,
179 1, __ATOMIC_RELAXED);
180 else if (!(old_bmap & (1UL << id)))
181 /* Someone else unregistered this thread.
182 * Counter should not be incremented.
185 } while (success == 0);
190 /* Wait till the reader threads have entered quiescent state. */
192 rte_rcu_qsbr_synchronize(struct rte_rcu_qsbr *v, unsigned int thread_id)
196 RTE_ASSERT(v != NULL);
198 t = rte_rcu_qsbr_start(v);
200 /* If the current thread has readside critical section,
201 * update its quiescent state status.
203 if (thread_id != RTE_QSBR_THRID_INVALID)
204 rte_rcu_qsbr_quiescent(v, thread_id);
206 /* Wait for other readers to enter quiescent state */
207 rte_rcu_qsbr_check(v, t, true);
210 /* Dump the details of a single quiescent state variable to a file. */
212 rte_rcu_qsbr_dump(FILE *f, struct rte_rcu_qsbr *v)
217 if (v == NULL || f == NULL) {
218 rte_log(RTE_LOG_ERR, rte_rcu_log_type,
219 "%s(): Invalid input parameter\n", __func__);
225 fprintf(f, "\nQuiescent State Variable @%p\n", v);
227 fprintf(f, " QS variable memory size = %zu\n",
228 rte_rcu_qsbr_get_memsize(v->max_threads));
229 fprintf(f, " Given # max threads = %u\n", v->max_threads);
230 fprintf(f, " Current # threads = %u\n", v->num_threads);
232 fprintf(f, " Registered thread IDs = ");
233 for (i = 0; i < v->num_elems; i++) {
234 bmap = __atomic_load_n(__RTE_QSBR_THRID_ARRAY_ELM(v, i),
236 id = i << __RTE_QSBR_THRID_INDEX_SHIFT;
238 t = __builtin_ctzl(bmap);
239 fprintf(f, "%u ", id + t);
247 fprintf(f, " Token = %"PRIu64"\n",
248 __atomic_load_n(&v->token, __ATOMIC_ACQUIRE));
250 fprintf(f, " Least Acknowledged Token = %"PRIu64"\n",
251 __atomic_load_n(&v->acked_token, __ATOMIC_ACQUIRE));
253 fprintf(f, "Quiescent State Counts for readers:\n");
254 for (i = 0; i < v->num_elems; i++) {
255 bmap = __atomic_load_n(__RTE_QSBR_THRID_ARRAY_ELM(v, i),
257 id = i << __RTE_QSBR_THRID_INDEX_SHIFT;
259 t = __builtin_ctzl(bmap);
260 fprintf(f, "thread ID = %u, count = %"PRIu64", lock count = %u\n",
263 &v->qsbr_cnt[id + t].cnt,
266 &v->qsbr_cnt[id + t].lock_cnt,
275 /* Create a queue used to store the data structure elements that can
276 * be freed later. This queue is referred to as 'defer queue'.
278 struct rte_rcu_qsbr_dq *
279 rte_rcu_qsbr_dq_create(const struct rte_rcu_qsbr_dq_parameters *params)
281 struct rte_rcu_qsbr_dq *dq;
282 uint32_t qs_fifo_size;
285 if (params == NULL || params->free_fn == NULL ||
286 params->v == NULL || params->name == NULL ||
287 params->size == 0 || params->esize == 0 ||
288 (params->esize % 4 != 0)) {
289 rte_log(RTE_LOG_ERR, rte_rcu_log_type,
290 "%s(): Invalid input parameter\n", __func__);
295 /* If auto reclamation is configured, reclaim limit
296 * should be a valid value.
298 if ((params->trigger_reclaim_limit <= params->size) &&
299 (params->max_reclaim_size == 0)) {
300 rte_log(RTE_LOG_ERR, rte_rcu_log_type,
301 "%s(): Invalid input parameter, size = %u, trigger_reclaim_limit = %u, max_reclaim_size = %u\n",
302 __func__, params->size, params->trigger_reclaim_limit,
303 params->max_reclaim_size);
309 dq = rte_zmalloc(NULL, sizeof(struct rte_rcu_qsbr_dq),
310 RTE_CACHE_LINE_SIZE);
317 /* Decide the flags for the ring.
318 * If MT safety is requested, use RTS for ring enqueue as most
319 * use cases involve dq-enqueue happening on the control plane.
320 * Ring dequeue is always HTS due to the possibility of revert.
322 flags = RING_F_MP_RTS_ENQ;
323 if (params->flags & RTE_RCU_QSBR_DQ_MT_UNSAFE)
324 flags = RING_F_SP_ENQ;
325 flags |= RING_F_MC_HTS_DEQ;
326 /* round up qs_fifo_size to next power of two that is not less than
329 qs_fifo_size = rte_align32pow2(params->size + 1);
330 /* Add token size to ring element size */
331 dq->r = rte_ring_create_elem(params->name,
332 __RTE_QSBR_TOKEN_SIZE + params->esize,
333 qs_fifo_size, SOCKET_ID_ANY, flags);
335 rte_log(RTE_LOG_ERR, rte_rcu_log_type,
336 "%s(): defer queue create failed\n", __func__);
342 dq->size = params->size;
343 dq->esize = __RTE_QSBR_TOKEN_SIZE + params->esize;
344 dq->trigger_reclaim_limit = params->trigger_reclaim_limit;
345 dq->max_reclaim_size = params->max_reclaim_size;
346 dq->free_fn = params->free_fn;
352 /* Enqueue one resource to the defer queue to free after the grace
355 int rte_rcu_qsbr_dq_enqueue(struct rte_rcu_qsbr_dq *dq, void *e)
357 __rte_rcu_qsbr_dq_elem_t *dq_elem;
360 if (dq == NULL || e == NULL) {
361 rte_log(RTE_LOG_ERR, rte_rcu_log_type,
362 "%s(): Invalid input parameter\n", __func__);
368 char data[dq->esize];
369 dq_elem = (__rte_rcu_qsbr_dq_elem_t *)data;
370 /* Start the grace period */
371 dq_elem->token = rte_rcu_qsbr_start(dq->v);
373 /* Reclaim resources if the queue size has hit the reclaim
374 * limit. This helps the queue from growing too large and
375 * allows time for reader threads to report their quiescent state.
377 cur_size = rte_ring_count(dq->r);
378 if (cur_size > dq->trigger_reclaim_limit) {
379 rte_log(RTE_LOG_INFO, rte_rcu_log_type,
380 "%s(): Triggering reclamation\n", __func__);
381 rte_rcu_qsbr_dq_reclaim(dq, dq->max_reclaim_size,
385 /* Enqueue the token and resource. Generating the token and
386 * enqueuing (token + resource) on the queue is not an
387 * atomic operation. When the defer queue is shared by multiple
388 * writers, this might result in tokens enqueued out of order
389 * on the queue. So, some tokens might wait longer than they
390 * are required to be reclaimed.
392 memcpy(dq_elem->elem, e, dq->esize - __RTE_QSBR_TOKEN_SIZE);
393 /* Check the status as enqueue might fail since the other threads
394 * might have used up the freed space.
395 * Enqueue uses the configured flags when the DQ was created.
397 if (rte_ring_enqueue_elem(dq->r, data, dq->esize) != 0) {
398 rte_log(RTE_LOG_ERR, rte_rcu_log_type,
399 "%s(): Enqueue failed\n", __func__);
400 /* Note that the token generated above is not used.
401 * Other than wasting tokens, it should not cause any
404 rte_log(RTE_LOG_INFO, rte_rcu_log_type,
405 "%s(): Skipped enqueuing token = %"PRIu64"\n",
406 __func__, dq_elem->token);
412 rte_log(RTE_LOG_INFO, rte_rcu_log_type,
413 "%s(): Enqueued token = %"PRIu64"\n", __func__, dq_elem->token);
418 /* Reclaim resources from the defer queue. */
420 rte_rcu_qsbr_dq_reclaim(struct rte_rcu_qsbr_dq *dq, unsigned int n,
421 unsigned int *freed, unsigned int *pending,
422 unsigned int *available)
425 __rte_rcu_qsbr_dq_elem_t *dq_elem;
427 if (dq == NULL || n == 0) {
428 rte_log(RTE_LOG_ERR, rte_rcu_log_type,
429 "%s(): Invalid input parameter\n", __func__);
437 char data[dq->esize];
438 /* Check reader threads quiescent state and reclaim resources */
440 rte_ring_dequeue_bulk_elem_start(dq->r, &data,
441 dq->esize, 1, available) != 0) {
442 dq_elem = (__rte_rcu_qsbr_dq_elem_t *)data;
444 /* Reclaim the resource */
445 if (rte_rcu_qsbr_check(dq->v, dq_elem->token, false) != 1) {
446 rte_ring_dequeue_elem_finish(dq->r, 0);
449 rte_ring_dequeue_elem_finish(dq->r, 1);
451 rte_log(RTE_LOG_INFO, rte_rcu_log_type,
452 "%s(): Reclaimed token = %"PRIu64"\n",
453 __func__, dq_elem->token);
455 dq->free_fn(dq->p, dq_elem->elem, 1);
460 rte_log(RTE_LOG_INFO, rte_rcu_log_type,
461 "%s(): Reclaimed %u resources\n", __func__, cnt);
466 *pending = rte_ring_count(dq->r);
471 /* Delete a defer queue. */
473 rte_rcu_qsbr_dq_delete(struct rte_rcu_qsbr_dq *dq)
475 unsigned int pending;
478 rte_log(RTE_LOG_DEBUG, rte_rcu_log_type,
479 "%s(): Invalid input parameter\n", __func__);
484 /* Reclaim all the resources */
485 rte_rcu_qsbr_dq_reclaim(dq, ~0, NULL, &pending, NULL);
492 rte_ring_free(dq->r);
498 RTE_LOG_REGISTER(rte_rcu_log_type, lib.rcu, ERR);