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 #include <rte_common.h> 31 #include <rte_pause.h> 32 #include <rte_stdatomic.h> 33 34 #ifdef __cplusplus 35 extern "C" { 36 #endif 37 38 /** 39 * The rte_pflock_t type. 40 */ 41 struct rte_pflock { 42 struct { 43 RTE_ATOMIC(uint16_t) in; 44 RTE_ATOMIC(uint16_t) out; 45 } rd, wr; 46 }; 47 typedef struct rte_pflock rte_pflock_t; 48 49 /* 50 * Allocation of bits to reader 51 * 52 * 15 4 3 2 1 0 53 * +-------------------+---+-+-+ 54 * | rin: reads issued |x|x| | | 55 * +-------------------+---+-+-+ 56 * ^ ^ 57 * | | 58 * PRES: writer present ----/ | 59 * PHID: writer phase id -----/ 60 * 61 * 15 4 3 2 1 0 62 * +------------------+------+ 63 * |rout:read complete|unused| 64 * +------------------+------+ 65 * 66 * The maximum number of readers is 4095 67 */ 68 69 /* Constants used to map the bits in reader counter */ 70 #define RTE_PFLOCK_WBITS 0x3 /* Writer bits in reader. */ 71 #define RTE_PFLOCK_PRES 0x2 /* Writer present bit. */ 72 #define RTE_PFLOCK_PHID 0x1 /* Phase ID bit. */ 73 #define RTE_PFLOCK_LSB 0xFFF0 /* reader bits. */ 74 #define RTE_PFLOCK_RINC 0x10 /* Reader increment. */ 75 76 /** 77 * A static pflock initializer. 78 */ 79 #define RTE_PFLOCK_INITIALIZER { } 80 81 /** 82 * Initialize the pflock to an unlocked state. 83 * 84 * @param pf 85 * A pointer to the pflock. 86 */ 87 static inline void 88 rte_pflock_init(struct rte_pflock *pf) 89 { 90 pf->rd.in = 0; 91 pf->rd.out = 0; 92 pf->wr.in = 0; 93 pf->wr.out = 0; 94 } 95 96 /** 97 * Take a pflock for read. 98 * 99 * @param pf 100 * A pointer to a pflock structure. 101 */ 102 static inline void 103 rte_pflock_read_lock(rte_pflock_t *pf) 104 { 105 uint16_t w; 106 107 /* 108 * If no writer is present, then the operation has completed 109 * successfully. 110 */ 111 w = rte_atomic_fetch_add_explicit(&pf->rd.in, RTE_PFLOCK_RINC, rte_memory_order_acquire) 112 & RTE_PFLOCK_WBITS; 113 if (w == 0) 114 return; 115 116 /* Wait for current write phase to complete. */ 117 RTE_WAIT_UNTIL_MASKED(&pf->rd.in, RTE_PFLOCK_WBITS, !=, w, rte_memory_order_acquire); 118 } 119 120 /** 121 * Release a pflock locked for reading. 122 * 123 * @param pf 124 * A pointer to the pflock structure. 125 */ 126 static inline void 127 rte_pflock_read_unlock(rte_pflock_t *pf) 128 { 129 rte_atomic_fetch_add_explicit(&pf->rd.out, RTE_PFLOCK_RINC, rte_memory_order_release); 130 } 131 132 /** 133 * Take the pflock for write. 134 * 135 * @param pf 136 * A pointer to the pflock structure. 137 */ 138 static inline void 139 rte_pflock_write_lock(rte_pflock_t *pf) 140 { 141 uint16_t ticket, w; 142 143 /* Acquire ownership of write-phase. 144 * This is same as rte_ticketlock_lock(). 145 */ 146 ticket = rte_atomic_fetch_add_explicit(&pf->wr.in, 1, rte_memory_order_relaxed); 147 rte_wait_until_equal_16((uint16_t *)(uintptr_t)&pf->wr.out, ticket, 148 rte_memory_order_acquire); 149 150 /* 151 * Acquire ticket on read-side in order to allow them 152 * to flush. Indicates to any incoming reader that a 153 * write-phase is pending. 154 * 155 * The load of rd.out in wait loop could be executed 156 * speculatively. 157 */ 158 w = RTE_PFLOCK_PRES | (ticket & RTE_PFLOCK_PHID); 159 ticket = rte_atomic_fetch_add_explicit(&pf->rd.in, w, rte_memory_order_relaxed); 160 161 /* Wait for any pending readers to flush. */ 162 rte_wait_until_equal_16((uint16_t *)(uintptr_t)&pf->rd.out, ticket, 163 rte_memory_order_acquire); 164 } 165 166 /** 167 * Release a pflock held for writing. 168 * 169 * @param pf 170 * A pointer to a pflock structure. 171 */ 172 static inline void 173 rte_pflock_write_unlock(rte_pflock_t *pf) 174 { 175 /* Migrate from write phase to read phase. */ 176 rte_atomic_fetch_and_explicit(&pf->rd.in, RTE_PFLOCK_LSB, rte_memory_order_release); 177 178 /* Allow other writers to continue. */ 179 rte_atomic_fetch_add_explicit(&pf->wr.out, 1, rte_memory_order_release); 180 } 181 182 #ifdef __cplusplus 183 } 184 #endif 185 186 #endif /* RTE_PFLOCK_H */ 187