xref: /dpdk/lib/eal/include/rte_pflock.h (revision 42a8fc7daa46256d150278fc9a7a846e27945a0c)
1 /* SPDX-License-Identifier: BSD-3-Clause
2  * Copyright(c) 2021 Microsoft Corp.
3  * All rights reserved.
4  *
5  * Derived from Concurrency Kit
6  * Copyright 2011-2015 Samy Al Bahra.
7  */
8 
9 #ifndef _RTE_PFLOCK_H_
10 #define _RTE_PFLOCK_H_
11 
12 /**
13  * @file
14  *
15  * Phase-fair locks
16  *
17  * This file defines an API for phase-fair reader writer locks,
18  * which is a variant of typical reader-writer locks that prevent
19  * starvation. In this type of lock, readers and writers alternate.
20  * This significantly reduces the worst-case blocking for readers and writers.
21  *
22  * This is an implementation derived from FreeBSD
23  * based on the work described in:
24  *    Brandenburg, B. and Anderson, J. 2010. Spin-Based
25  *    Reader-Writer Synchronization for Multiprocessor Real-Time Systems
26  *
27  * All locks must be initialised before use, and only initialised once.
28  */
29 
30 #ifdef __cplusplus
31 extern "C" {
32 #endif
33 
34 #include <rte_common.h>
35 #include <rte_pause.h>
36 
37 /**
38  * The rte_pflock_t type.
39  */
40 struct rte_pflock {
41 	struct {
42 		uint16_t in;
43 		uint16_t out;
44 	} rd, wr;
45 };
46 typedef struct rte_pflock rte_pflock_t;
47 
48 /*
49  * Allocation of bits to reader
50  *
51  * 15                 4 3 2 1 0
52  * +-------------------+---+-+-+
53  * | rin: reads issued |x|x| | |
54  * +-------------------+---+-+-+
55  *                          ^ ^
56  *                          | |
57  * PRES: writer present ----/ |
58  * PHID: writer phase id -----/
59  *
60  * 15                4 3 2 1 0
61  * +------------------+------+
62  * |rout:read complete|unused|
63  * +------------------+------+
64  *
65  * The maximum number of readers is 4095
66  */
67 
68 /* Constants used to map the bits in reader counter */
69 #define RTE_PFLOCK_WBITS 0x3	/* Writer bits in reader. */
70 #define RTE_PFLOCK_PRES  0x2	/* Writer present bit. */
71 #define RTE_PFLOCK_PHID  0x1	/* Phase ID bit. */
72 #define RTE_PFLOCK_LSB   0xFFF0 /* reader bits. */
73 #define RTE_PFLOCK_RINC  0x10	/* Reader increment. */
74 
75 /**
76  * A static pflock initializer.
77  */
78 #define RTE_PFLOCK_INITIALIZER {  }
79 
80 /**
81  * @warning
82  * @b EXPERIMENTAL: this API may change without prior notice.
83  *
84  * Initialize the pflock to an unlocked state.
85  *
86  * @param pf
87  *   A pointer to the pflock.
88  */
89 __rte_experimental
90 static inline void
91 rte_pflock_init(struct rte_pflock *pf)
92 {
93 	pf->rd.in = 0;
94 	pf->rd.out = 0;
95 	pf->wr.in = 0;
96 	pf->wr.out = 0;
97 }
98 
99 /**
100  * @warning
101  * @b EXPERIMENTAL: this API may change without prior notice.
102  *
103  * Take a pflock for read.
104  *
105  * @param pf
106  *   A pointer to a pflock structure.
107  */
108 __rte_experimental
109 static inline void
110 rte_pflock_read_lock(rte_pflock_t *pf)
111 {
112 	uint16_t w;
113 
114 	/*
115 	 * If no writer is present, then the operation has completed
116 	 * successfully.
117 	 */
118 	w = __atomic_fetch_add(&pf->rd.in, RTE_PFLOCK_RINC, __ATOMIC_ACQUIRE)
119 		& RTE_PFLOCK_WBITS;
120 	if (w == 0)
121 		return;
122 
123 	/* Wait for current write phase to complete. */
124 	RTE_WAIT_UNTIL_MASKED(&pf->rd.in, RTE_PFLOCK_WBITS, !=, w,
125 		__ATOMIC_ACQUIRE);
126 }
127 
128 /**
129  * @warning
130  * @b EXPERIMENTAL: this API may change without prior notice.
131  *
132  * Release a pflock locked for reading.
133  *
134  * @param pf
135  *   A pointer to the pflock structure.
136  */
137 __rte_experimental
138 static inline void
139 rte_pflock_read_unlock(rte_pflock_t *pf)
140 {
141 	__atomic_fetch_add(&pf->rd.out, RTE_PFLOCK_RINC, __ATOMIC_RELEASE);
142 }
143 
144 /**
145  * @warning
146  * @b EXPERIMENTAL: this API may change without prior notice.
147  *
148  * Take the pflock for write.
149  *
150  * @param pf
151  *   A pointer to the pflock structure.
152  */
153 __rte_experimental
154 static inline void
155 rte_pflock_write_lock(rte_pflock_t *pf)
156 {
157 	uint16_t ticket, w;
158 
159 	/* Acquire ownership of write-phase.
160 	 * This is same as rte_ticketlock_lock().
161 	 */
162 	ticket = __atomic_fetch_add(&pf->wr.in, 1, __ATOMIC_RELAXED);
163 	rte_wait_until_equal_16(&pf->wr.out, ticket, __ATOMIC_ACQUIRE);
164 
165 	/*
166 	 * Acquire ticket on read-side in order to allow them
167 	 * to flush. Indicates to any incoming reader that a
168 	 * write-phase is pending.
169 	 *
170 	 * The load of rd.out in wait loop could be executed
171 	 * speculatively.
172 	 */
173 	w = RTE_PFLOCK_PRES | (ticket & RTE_PFLOCK_PHID);
174 	ticket = __atomic_fetch_add(&pf->rd.in, w, __ATOMIC_RELAXED);
175 
176 	/* Wait for any pending readers to flush. */
177 	rte_wait_until_equal_16(&pf->rd.out, ticket, __ATOMIC_ACQUIRE);
178 }
179 
180 /**
181  * @warning
182  * @b EXPERIMENTAL: this API may change without prior notice.
183  *
184  * Release a pflock held for writing.
185  *
186  * @param pf
187  *   A pointer to a pflock structure.
188  */
189 __rte_experimental
190 static inline void
191 rte_pflock_write_unlock(rte_pflock_t *pf)
192 {
193 	/* Migrate from write phase to read phase. */
194 	__atomic_fetch_and(&pf->rd.in, RTE_PFLOCK_LSB, __ATOMIC_RELEASE);
195 
196 	/* Allow other writers to continue. */
197 	__atomic_fetch_add(&pf->wr.out, 1, __ATOMIC_RELEASE);
198 }
199 
200 #ifdef __cplusplus
201 }
202 #endif
203 
204 #endif /* RTE_PFLOCK_H */
205