[ceph.git] / ceph / src / spdk / dpdk / lib / librte_stack / rte_stack_lf_generic.h

/* 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.
	 */
	return (unsigned int)rte_atomic64_read((rte_atomic64_t *)
			&s->stack_lf.used.len);
}

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, __ATOMIC_RELEASE,
				__ATOMIC_RELAXED);
	} while (success == 0);

	rte_atomic64_add((rte_atomic64_t *)&list->len, num);
}

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;

	/* Reserve num elements, if available */
	while (1) {
		uint64_t len = rte_atomic64_read((rte_atomic64_t *)&list->len);

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

		if (rte_atomic64_cmpset((volatile uint64_t *)&list->len,
					len, len - num))
			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)
			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, __ATOMIC_RELEASE,
				__ATOMIC_RELAXED);
	} while (success == 0);

	return old_head.top;
}

#endif /* _RTE_STACK_LF_GENERIC_H_ */
Commit	Line	Data
9f95a23c TL	1	/* SPDX-License-Identifier: BSD-3-Clause
	2	* Copyright(c) 2019 Intel Corporation
	3	*/
	4
	5	#ifndef _RTE_STACK_LF_GENERIC_H_
	6	#define _RTE_STACK_LF_GENERIC_H_
	7
	8	#include <rte_branch_prediction.h>
	9	#include <rte_prefetch.h>
	10
	11	static __rte_always_inline unsigned int
	12	__rte_stack_lf_count(struct rte_stack *s)
	13	{
	14	/* stack_lf_push() and stack_lf_pop() do not update the list's contents
	15	* and stack_lf->len atomically, which can cause the list to appear
	16	* shorter than it actually is if this function is called while other
	17	* threads are modifying the list.
	18	*
	19	* However, given the inherently approximate nature of the get_count
	20	* callback -- even if the list and its size were updated atomically,
	21	* the size could change between when get_count executes and when the
	22	* value is returned to the caller -- this is acceptable.
	23	*
	24	* The stack_lf->len updates are placed such that the list may appear to
	25	* have fewer elements than it does, but will never appear to have more
	26	* elements. If the mempool is near-empty to the point that this is a
	27	* concern, the user should consider increasing the mempool size.
	28	*/
f67539c2 TL	29	return (unsigned int)rte_atomic64_read((rte_atomic64_t *)
f67539c2 TL	30	&s->stack_lf.used.len);
9f95a23c TL	31	}
	32
	33	static __rte_always_inline void
	34	__rte_stack_lf_push_elems(struct rte_stack_lf_list *list,
	35	struct rte_stack_lf_elem *first,
	36	struct rte_stack_lf_elem *last,
	37	unsigned int num)
	38	{
9f95a23c TL	39	struct rte_stack_lf_head old_head;
	40	int success;
	41
	42	old_head = list->head;
	43
	44	do {
	45	struct rte_stack_lf_head new_head;
	46
	47	/* An acquire fence (or stronger) is needed for weak memory
	48	* models to establish a synchronized-with relationship between
	49	* the list->head load and store-release operations (as part of
	50	* the rte_atomic128_cmp_exchange()).
	51	*/
	52	rte_smp_mb();
	53
	54	/* Swing the top pointer to the first element in the list and
	55	* make the last element point to the old top.
	56	*/
	57	new_head.top = first;
	58	new_head.cnt = old_head.cnt + 1;
	59
	60	last->next = old_head.top;
	61
	62	/* old_head is updated on failure */
	63	success = rte_atomic128_cmp_exchange(
	64	(rte_int128_t *)&list->head,
	65	(rte_int128_t *)&old_head,
	66	(rte_int128_t *)&new_head,
	67	1, __ATOMIC_RELEASE,
	68	__ATOMIC_RELAXED);
	69	} while (success == 0);
	70
f67539c2	71	rte_atomic64_add((rte_atomic64_t *)&list->len, num);
9f95a23c TL	72	}
	73
	74	static __rte_always_inline struct rte_stack_lf_elem *
	75	__rte_stack_lf_pop_elems(struct rte_stack_lf_list *list,
	76	unsigned int num,
	77	void **obj_table,
	78	struct rte_stack_lf_elem **last)
	79	{
9f95a23c TL	80	struct rte_stack_lf_head old_head;
	81	int success;
	82
	83	/* Reserve num elements, if available */
	84	while (1) {
f67539c2	85	uint64_t len = rte_atomic64_read((rte_atomic64_t *)&list->len);
9f95a23c TL	86
	87	/* Does the list contain enough elements? */
	88	if (unlikely(len < num))
	89	return NULL;
	90
	91	if (rte_atomic64_cmpset((volatile uint64_t *)&list->len,
	92	len, len - num))
	93	break;
	94	}
	95
	96	old_head = list->head;
	97
	98	/* Pop num elements */
	99	do {
	100	struct rte_stack_lf_head new_head;
	101	struct rte_stack_lf_elem *tmp;
	102	unsigned int i;
	103
	104	/* An acquire fence (or stronger) is needed for weak memory
	105	* models to ensure the LF LIFO element reads are properly
	106	* ordered with respect to the head pointer read.
	107	*/
	108	rte_smp_mb();
	109
	110	rte_prefetch0(old_head.top);
	111
	112	tmp = old_head.top;
	113
	114	/* Traverse the list to find the new head. A next pointer will
	115	* either point to another element or NULL; if a thread
	116	* encounters a pointer that has already been popped, the CAS
	117	* will fail.
	118	*/
	119	for (i = 0; i < num && tmp != NULL; i++) {
	120	rte_prefetch0(tmp->next);
	121	if (obj_table)
	122	obj_table[i] = tmp->data;
	123	if (last)
	124	*last = tmp;
	125	tmp = tmp->next;
	126	}
	127
	128	/* If NULL was encountered, the list was modified while
	129	* traversing it. Retry.
	130	*/
	131	if (i != num)
	132	continue;
	133
	134	new_head.top = tmp;
	135	new_head.cnt = old_head.cnt + 1;
	136
	137	/* old_head is updated on failure */
	138	success = rte_atomic128_cmp_exchange(
	139	(rte_int128_t *)&list->head,
	140	(rte_int128_t *)&old_head,
	141	(rte_int128_t *)&new_head,
	142	1, __ATOMIC_RELEASE,
	143	__ATOMIC_RELAXED);
	144	} while (success == 0);
	145
	146	return old_head.top;
9f95a23c TL	147	}
	148
	149	#endif /* _RTE_STACK_LF_GENERIC_H_ */