xref: /dpdk/lib/stack/rte_stack_lf_generic.h (revision b6a19ec1400c750288cc643a64eabd41b9342af8)

/* SPDX-License-Identifier: BSD-3-Clause
 * Copyright(c) 2019 Intel Corporation
 */

#ifndef _RTE_STACK_LF_GENERIC_H_
#define _RTE_STACK_LF_GENERIC_H_

#include <rte_branch_prediction.h>
#include <rte_prefetch.h>

static __rte_always_inline unsigned int
__rte_stack_lf_count(struct rte_stack *s)
{
	/* stack_lf_push() and stack_lf_pop() do not update the list's contents
	 * and stack_lf->len atomically, which can cause the list to appear
	 * shorter than it actually is if this function is called while other
	 * threads are modifying the list.
	 *
	 * However, given the inherently approximate nature of the get_count
	 * callback -- even if the list and its size were updated atomically,
	 * the size could change between when get_count executes and when the
	 * value is returned to the caller -- this is acceptable.
	 *
	 * The stack_lf->len updates are placed such that the list may appear to
	 * have fewer elements than it does, but will never appear to have more
	 * elements. If the mempool is near-empty to the point that this is a
	 * concern, the user should consider increasing the mempool size.
	 */
	/* NOTE: review for potential ordering optimization */
	return rte_atomic_load_explicit(&s->stack_lf.used.len, rte_memory_order_seq_cst);
}

static __rte_always_inline void
__rte_stack_lf_push_elems(struct rte_stack_lf_list *list,
			  struct rte_stack_lf_elem *first,
			  struct rte_stack_lf_elem *last,
			  unsigned int num)
{
	struct rte_stack_lf_head old_head;
	int success;

	old_head = list->head;

	do {
		struct rte_stack_lf_head new_head;

		/* An acquire fence (or stronger) is needed for weak memory
		 * models to establish a synchronized-with relationship between
		 * the list->head load and store-release operations (as part of
		 * the rte_atomic128_cmp_exchange()).
		 */
		rte_smp_mb();

		/* Swing the top pointer to the first element in the list and
		 * make the last element point to the old top.
		 */
		new_head.top = first;
		new_head.cnt = old_head.cnt + 1;

		last->next = old_head.top;

		/* old_head is updated on failure */
		success = rte_atomic128_cmp_exchange(
				(rte_int128_t *)&list->head,
				(rte_int128_t *)&old_head,
				(rte_int128_t *)&new_head,
				1, rte_memory_order_release,
				rte_memory_order_relaxed);
	} while (success == 0);
	/* NOTE: review for potential ordering optimization */
	rte_atomic_fetch_add_explicit(&list->len, num, rte_memory_order_seq_cst);
}

static __rte_always_inline struct rte_stack_lf_elem *
__rte_stack_lf_pop_elems(struct rte_stack_lf_list *list,
			 unsigned int num,
			 void **obj_table,
			 struct rte_stack_lf_elem **last)
{
	struct rte_stack_lf_head old_head;
	int success = 0;

	/* Reserve num elements, if available */
	while (1) {
		/* NOTE: review for potential ordering optimization */
		uint64_t len = rte_atomic_load_explicit(&list->len, rte_memory_order_seq_cst);

		/* Does the list contain enough elements? */
		if (unlikely(len < num))
			return NULL;

		/* NOTE: review for potential ordering optimization */
		if (rte_atomic_compare_exchange_strong_explicit(&list->len, &len, len - num,
				rte_memory_order_seq_cst, rte_memory_order_seq_cst))
			break;
	}

	old_head = list->head;

	/* Pop num elements */
	do {
		struct rte_stack_lf_head new_head;
		struct rte_stack_lf_elem *tmp;
		unsigned int i;

		/* An acquire fence (or stronger) is needed for weak memory
		 * models to ensure the LF LIFO element reads are properly
		 * ordered with respect to the head pointer read.
		 */
		rte_smp_mb();

		rte_prefetch0(old_head.top);

		tmp = old_head.top;

		/* Traverse the list to find the new head. A next pointer will
		 * either point to another element or NULL; if a thread
		 * encounters a pointer that has already been popped, the CAS
		 * will fail.
		 */
		for (i = 0; i < num && tmp != NULL; i++) {
			rte_prefetch0(tmp->next);
			if (obj_table)
				obj_table[i] = tmp->data;
			if (last)
				*last = tmp;
			tmp = tmp->next;
		}

		/* If NULL was encountered, the list was modified while
		 * traversing it. Retry.
		 */
		if (i != num) {
			old_head = list->head;
			continue;
		}

		new_head.top = tmp;
		new_head.cnt = old_head.cnt + 1;

		/* old_head is updated on failure */
		success = rte_atomic128_cmp_exchange(
				(rte_int128_t *)&list->head,
				(rte_int128_t *)&old_head,
				(rte_int128_t *)&new_head,
				1, rte_memory_order_release,
				rte_memory_order_relaxed);
	} while (success == 0);

	return old_head.top;
}

#endif /* _RTE_STACK_LF_GENERIC_H_ */