[libside.git] / src / rcu.h

// SPDX-License-Identifier: MIT
/*
 * Copyright 2022 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
 */

#include <sched.h>
#include <stdint.h>
#include <pthread.h>
#include <poll.h>

#define SIDE_CACHE_LINE_SIZE		256
#define SIDE_RCU_PERCPU_ARRAY_SIZE	2

struct side_rcu_percpu_count {
	uintptr_t begin;
	uintptr_t end;
}  __attribute__((__aligned__(SIDE_CACHE_LINE_SIZE)));

struct side_rcu_cpu_gp_state {
	struct side_rcu_percpu_count count[SIDE_RCU_PERCPU_ARRAY_SIZE];
};

struct side_rcu_gp_state {
	struct side_rcu_cpu_gp_state *percpu_state;
	int nr_cpus;
	unsigned int period;
	pthread_mutex_t gp_lock;
};

//TODO: replace atomics by rseq (when available)
//TODO: replace acquire/release by membarrier+compiler barrier (when available)
//TODO: implement wait/wakeup for grace period using sys_futex
static inline
unsigned int side_rcu_read_begin(struct side_rcu_gp_state *gp_state)
{
	int cpu = sched_getcpu();
	unsigned int period = __atomic_load_n(&gp_state->period, __ATOMIC_RELAXED);

	if (cpu < 0)
		cpu = 0;
	/*
	 * This acquire MO pairs with the release fence at the end of
	 * side_rcu_wait_grace_period().
	 */
	(void) __atomic_add_fetch(&gp_state->percpu_state[cpu].count[period].begin, 1, __ATOMIC_ACQUIRE);
	return period;
}

static inline
void side_rcu_read_end(struct side_rcu_gp_state *gp_state, unsigned int period)
{
	int cpu = sched_getcpu();

	if (cpu < 0)
		cpu = 0;
	/*
	 * This release MO pairs with the acquire fence at the beginning
	 * of side_rcu_wait_grace_period().
	 */
	(void) __atomic_add_fetch(&gp_state->percpu_state[cpu].count[period].end, 1, __ATOMIC_RELEASE);
}

static inline
void wait_for_cpus(struct side_rcu_gp_state *gp_state)
{
	unsigned int prev_period = 1 - gp_state->period;

	/*
	 * Wait for the sum of CPU begin/end counts to match for the
	 * previous period.
	 */
	for (;;) {
		uintptr_t sum = 0;	/* begin - end */
		int i;

		for (i = 0; i < gp_state->nr_cpus; i++) {
			struct side_rcu_cpu_gp_state *cpu_state = &gp_state->percpu_state[i];

			sum -= __atomic_load_n(&cpu_state->count[prev_period].end, __ATOMIC_RELAXED);
		}

		/*
		 * Read end counts before begin counts. Reading end
		 * before begin count ensures we never see an end
		 * without having seen its associated begin, in case of
		 * a thread migration during the traversal over each
		 * cpu.
		 */
		__atomic_thread_fence(__ATOMIC_SEQ_CST);

		for (i = 0; i < gp_state->nr_cpus; i++) {
			struct side_rcu_cpu_gp_state *cpu_state = &gp_state->percpu_state[i];

			sum += __atomic_load_n(&cpu_state->count[prev_period].begin, __ATOMIC_RELAXED);
		}
		if (!sum) {
			break;
		} else {
			/* Retry after 10ms. */
			poll(NULL, 0, 10);
		}
	}
}

static inline
void side_rcu_wait_grace_period(struct side_rcu_gp_state *gp_state)
{
	/*
	 * This fence pairs with the acquire MO __atomic_add_fetch in
	 * side_rcu_read_begin().
	 */
	__atomic_thread_fence(__ATOMIC_SEQ_CST);

	pthread_mutex_lock(&gp_state->gp_lock);

	wait_for_cpus(gp_state);

	/* Flip period: 0 -> 1, 1 -> 0. */
	(void) __atomic_xor_fetch(&gp_state->period, 1, __ATOMIC_SEQ_CST);

	wait_for_cpus(gp_state);

	pthread_mutex_unlock(&gp_state->gp_lock);

	/*
	 * This fence pairs with the release MO __atomic_add_fetch in
	 * side_rcu_read_end().
	 */
	__atomic_thread_fence(__ATOMIC_SEQ_CST);
}
Commit	Line	Data
85b765b8 MD	1	// SPDX-License-Identifier: MIT
	2	/*
	3	* Copyright 2022 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
	4	*/
	5
	6	#include <sched.h>
	7	#include <stdint.h>
	8	#include <pthread.h>
	9	#include <poll.h>
	10
	11	#define SIDE_CACHE_LINE_SIZE 256
	12	#define SIDE_RCU_PERCPU_ARRAY_SIZE 2
	13
	14	struct side_rcu_percpu_count {
	15	uintptr_t begin;
	16	uintptr_t end;
	17	} __attribute__((__aligned__(SIDE_CACHE_LINE_SIZE)));
	18
	19	struct side_rcu_cpu_gp_state {
	20	struct side_rcu_percpu_count count[SIDE_RCU_PERCPU_ARRAY_SIZE];
	21	};
	22
	23	struct side_rcu_gp_state {
	24	struct side_rcu_cpu_gp_state *percpu_state;
	25	int nr_cpus;
	26	unsigned int period;
	27	pthread_mutex_t gp_lock;
	28	};
	29
	30	//TODO: replace atomics by rseq (when available)
	31	//TODO: replace acquire/release by membarrier+compiler barrier (when available)
	32	//TODO: implement wait/wakeup for grace period using sys_futex
	33	static inline
	34	unsigned int side_rcu_read_begin(struct side_rcu_gp_state *gp_state)
	35	{
	36	int cpu = sched_getcpu();
	37	unsigned int period = __atomic_load_n(&gp_state->period, __ATOMIC_RELAXED);
	38
	39	if (cpu < 0)
	40	cpu = 0;
117e507d MD	41	/*
	42	* This acquire MO pairs with the release fence at the end of
	43	* side_rcu_wait_grace_period().
	44	*/
85b765b8 MD	45	(void) __atomic_add_fetch(&gp_state->percpu_state[cpu].count[period].begin, 1, __ATOMIC_ACQUIRE);
	46	return period;
	47	}
	48
	49	static inline
	50	void side_rcu_read_end(struct side_rcu_gp_state *gp_state, unsigned int period)
	51	{
	52	int cpu = sched_getcpu();
	53
	54	if (cpu < 0)
	55	cpu = 0;
117e507d MD	56	/*
	57	* This release MO pairs with the acquire fence at the beginning
	58	* of side_rcu_wait_grace_period().
	59	*/
85b765b8 MD	60	(void) __atomic_add_fetch(&gp_state->percpu_state[cpu].count[period].end, 1, __ATOMIC_RELEASE);
	61	}
	62
	63	static inline
	64	void wait_for_cpus(struct side_rcu_gp_state *gp_state)
	65	{
	66	unsigned int prev_period = 1 - gp_state->period;
	67
	68	/*
	69	* Wait for the sum of CPU begin/end counts to match for the
	70	* previous period.
	71	*/
	72	for (;;) {
	73	uintptr_t sum = 0; /* begin - end */
	74	int i;
	75
	76	for (i = 0; i < gp_state->nr_cpus; i++) {
	77	struct side_rcu_cpu_gp_state *cpu_state = &gp_state->percpu_state[i];
	78
	79	sum -= __atomic_load_n(&cpu_state->count[prev_period].end, __ATOMIC_RELAXED);
	80	}
	81
	82	/*
	83	* Read end counts before begin counts. Reading end
	84	* before begin count ensures we never see an end
	85	* without having seen its associated begin, in case of
	86	* a thread migration during the traversal over each
	87	* cpu.
	88	*/
54251984	89	__atomic_thread_fence(__ATOMIC_SEQ_CST);
85b765b8 MD	90
	91	for (i = 0; i < gp_state->nr_cpus; i++) {
	92	struct side_rcu_cpu_gp_state *cpu_state = &gp_state->percpu_state[i];
	93
	94	sum += __atomic_load_n(&cpu_state->count[prev_period].begin, __ATOMIC_RELAXED);
	95	}
	96	if (!sum) {
	97	break;
	98	} else {
	99	/* Retry after 10ms. */
	100	poll(NULL, 0, 10);
	101	}
	102	}
	103	}
	104
	105	static inline
	106	void side_rcu_wait_grace_period(struct side_rcu_gp_state *gp_state)
	107	{
	108	/*
54251984 MD	109	* This fence pairs with the acquire MO __atomic_add_fetch in
54251984 MD	110	* side_rcu_read_begin().
85b765b8	111	*/
54251984	112	__atomic_thread_fence(__ATOMIC_SEQ_CST);
85b765b8 MD	113
	114	pthread_mutex_lock(&gp_state->gp_lock);
	115
	116	wait_for_cpus(gp_state);
	117
	118	/* Flip period: 0 -> 1, 1 -> 0. */
54251984	119	(void) __atomic_xor_fetch(&gp_state->period, 1, __ATOMIC_SEQ_CST);
85b765b8 MD	120
	121	wait_for_cpus(gp_state);
	122
	123	pthread_mutex_unlock(&gp_state->gp_lock);
	124
	125	/*
54251984 MD	126	* This fence pairs with the release MO __atomic_add_fetch in
54251984 MD	127	* side_rcu_read_end().
85b765b8	128	*/
54251984	129	__atomic_thread_fence(__ATOMIC_SEQ_CST);
85b765b8	130	}