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