1 krisbash 1.1 #include <stdlib.h>
2 #include <malloc.h>
3 #include "lock.h"
4 #include "atomic.h"
5 #include "sleep.h"
6 #include "cpu.h"
7 #include "memory.h"
8
9 #define CPU_MASK_UNINITIALIZED -1
10 #define CACHE_LINE_SIZE 128
11 #define LATCHES_PER_LINE 16
12 #define POOL_FULL_MASK 0xffff
13 #define POOL_LINES (s_cpuMask + 1)
14 #define POOL_SIZE (sizeof(CachedLock_Pool) + CACHE_LINE_SIZE * (POOL_LINES + 1))
15
16 #define ALIGN(x, size) (((x) + (size) - 1) & -(size))
17
18 /* Number of separate cache lines, minus 1, for easy masking. */
19 static int s_cpuMask = CPU_MASK_UNINITIALIZED;
20 static ptrdiff_t s_masterMask = 0;
21 static Lock s_latchPoolLock = LOCK_INITIALIZER;
22 krisbash 1.1 static CachedLock_Pool* s_currentPool = NULL;
23
24 #ifdef PAL_64BIT
25 # define MASTER_INCREMENT ((ptrdiff_t)1 << 32)
26 #else
27 # define MASTER_INCREMENT ((ptrdiff_t)1 << 16)
28 #endif
29
30 #define MASTER_MASK (MASTER_INCREMENT - 1)
31
32 static CachedLock_Pool* Pool_New()
33 {
34 CachedLock_Pool* pool;
35 ptrdiff_t buffer;
36
37 /* The pool and all the latch lines are one block. */
38 pool = (CachedLock_Pool*)PAL_Malloc(POOL_SIZE);
39 if (pool == NULL)
40 return NULL;
41
42 /* buffer contains an extra cache line for manual alignment. */
43 krisbash 1.1 buffer = (ptrdiff_t)(pool + 1);
44 buffer = ALIGN(buffer, CACHE_LINE_SIZE);
45
46 pool->latches = (ptrdiff_t*)buffer;
47 pool->mask = 0;
48
49 return pool;
50 }
51
52 static void Pool_Delete(
53 _In_ CachedLock_Pool* self
54 )
55 {
56 PAL_Free(self);
57 }
58
59 static void ATEXIT_API ShutdownCachePool(void)
60 {
61 if (s_currentPool)
62 Pool_Delete(s_currentPool);
63 s_currentPool = NULL;
64 krisbash 1.1 }
65
66 static void InitializeCachePool()
67 {
68 int cpus = CPU_GetCount();
69
70 /* Round up to the next power of two. */
71 if (cpus <= 1)
72 cpus = 1;
73 else if (cpus <= 2)
74 cpus = 2;
75 else if (cpus <= 4)
76 cpus = 4;
77 else if (cpus <= 8)
78 cpus = 8;
79 #ifdef PAL_64BIT
80 else if (cpus > 16)
81 cpus = 32;
82 #endif
83 else
84 cpus = 16;
85 krisbash 1.1
86 /* Everyone needs to mask off higher bits in case CPU_GetCurrent ever
87 * returns a number higher than it did now, or in case there are more than
88 * 32 CPUs. */
89 s_cpuMask = cpus - 1;
90 s_masterMask = ((ptrdiff_t)1 << cpus) - 1;
91 PAL_Atexit(ShutdownCachePool);
92 }
93
94 _Return_type_success_(return == 0) int CachedLock_Init_Checked(
95 _Out_ CachedLock* self,
96 unsigned long flags,
97 NitsCallSite cs
98 )
99 {
100 CachedLock_Pool* pool;
101 int index;
102 ReadWriteLock temp = READWRITELOCK_INITIALIZER;
103
104 /* One-time initialization. Doesn't matter if called several times. */
105 if (s_cpuMask == CPU_MASK_UNINITIALIZED)
106 krisbash 1.1 InitializeCachePool();
107
108 if (flags & CACHEDLOCK_FLAG_SHARED)
109 {
110 Lock_Acquire(&s_latchPoolLock);
111
112 if (NitsShouldFault(cs, NitsAutomatic))
113 return -1;
114
115 if (s_currentPool == NULL ||
116 s_currentPool->mask == POOL_FULL_MASK)
117 {
118 /* The current pool is full. */
119 s_currentPool = Pool_New();
120 if (s_currentPool == NULL)
121 return -1;
122 }
123
124 /* Search the pool for a zero bit. */
125 pool = s_currentPool;
126 for (index = 0; index < POOL_LINES; index++)
127 krisbash 1.1 if ((pool->mask & ((ptrdiff_t)1 << index)) == 0)
128 break;
129
130 /* Take ownership of this index. */
131 pool->mask |= ((ptrdiff_t)1 << index);
132 Lock_Release(&s_latchPoolLock);
133 }
134 else
135 {
136 pool = Pool_New();
137 if (pool == NULL)
138 return -1;
139 pool->mask = 1;
140 index = 0;
141 }
142
143 self->pool = pool;
144 self->latches = pool->latches + index;
145 self->lock = temp;
146 self->master = 0;
147
148 krisbash 1.1 return 0;
149 }
150
151 void CachedLock_Destroy(
152 _Inout_ CachedLock* self
153 )
154 {
155 CachedLock_Pool* pool = self->pool;
156 ptrdiff_t index = self->latches - self->pool->latches;
157
158 Lock_Acquire(&s_latchPoolLock);
159
160 /* Release ownership of our bit. */
161 pool->mask &= ~((ptrdiff_t)1 << index);
162
163 /* Determine if this pool has been orphaned. */
164 if (pool->mask == 0 && pool != s_currentPool)
165 Pool_Delete(pool);
166
167 Lock_Release(&s_latchPoolLock);
168 }
169 krisbash 1.1
170 static void ClearCPU(
171 _Inout_ CachedLock* self,
172 _Inout_ ptrdiff_t* latch)
173 {
174 ptrdiff_t index = (latch - self->latches) / LATCHES_PER_LINE;
175
176 /* There are exclusive threads acquiring.
177 * Mark this latch as empty in the central shared mask. */
178 ptrdiff_t result = Atomic_And(&self->master, ~((ptrdiff_t)1 << index));
179
180 if ((result & MASTER_MASK) == 0)
181 CondLock_Broadcast((ptrdiff_t)self);
182 }
183
184 static int TryAcquireRead(
185 _Inout_ CachedLock* self,
186 _Out_ void** token
187 )
188 {
189 volatile ptrdiff_t* master = &self->master;
190 krisbash 1.1 ptrdiff_t* latch;
191 int cpu;
192
193 cpu = CPU_GetCurrent() & s_cpuMask;
194 latch = self->latches + LATCHES_PER_LINE * cpu;
195
196 if (*master != 0)
197 {
198 /* Exclusive threads are already here. Short-circuit. */
199 *token = NULL;
200 return 0;
201 }
202
203 Atomic_Inc(latch);
204
205 if (*master != 0)
206 {
207 /* Exclusive threads might have missed our increment. */
208 if (Atomic_Dec(latch) == 0)
209 ClearCPU(self, latch);
210 *token = NULL;
211 krisbash 1.1 return 0;
212 }
213
214 /* Exclusive threads cannot miss that we are here. */
215 *token = latch;
216 return 1;
217 }
218
219 void CachedLock_AcquireRead(
220 _Inout_ CachedLock* self,
221 _Out_ void** token
222 )
223 {
224 if (TryAcquireRead(self, token) != 0)
225 return;
226
227 ReadWriteLock_AcquireRead(&self->lock);
228 }
229
230 void CachedLock_AcquireWrite(
231 _Inout_ CachedLock* self
232 krisbash 1.1 )
233 {
234 ptrdiff_t oldState, state, swapState;
235 ptrdiff_t oldMask, zeroMask, index;
236 volatile ptrdiff_t* master = &self->master;
237
238 /* The order of steps here is important.
239 * 1) Stop shared readers from racing through the latches.
240 * 2) Scan the latches to find inactive ones.
241 * 3) Get exclusive access to the central lock.
242 * 4) Wait for existing shared readers in the latches to leave.
243 *
244 * Doing (3) before (1) lets readers race through the latches if the
245 * central lock is still held by a reader from previous contention.
246 * Doing (3) before (2) leads to deadlock if there are no active latches
247 * and another writer gets the central lock first.
248 * Doing (3) after (4) lets readers race through the central lock. */
249
250 for (;;)
251 {
252 oldState = PAL_PREFETCH(master);
253 krisbash 1.1
254 /* The first thread atomically sets s_masterMask. */
255 if (oldState == 0)
256 state = s_masterMask + MASTER_INCREMENT;
257 else
258 state = oldState + MASTER_INCREMENT;
259
260 swapState = Atomic_CompareAndSwap(master, oldState, state);
261 if (swapState == oldState)
262 break;
263 }
264
265 /* Reader threads will now observe that master != 0. */
266
267 if (oldState == 0)
268 {
269 /* This is the thread that set s_masterMask. */
270 zeroMask = 0;
271 for (index = 0; index < POOL_LINES; index++)
272 {
273 /* Determine if all shared threads are gone. */
274 krisbash 1.1 if (self->latches[LATCHES_PER_LINE * index] == 0)
275 zeroMask |= ((ptrdiff_t)1 << index);
276 }
277
278 /* Determine if there are any CPUs with shared threads remaining.
279 * Other exclusive threads could be waiting. */
280 if ((Atomic_And(master, ~zeroMask) & MASTER_MASK) == 0)
281 CondLock_Broadcast((ptrdiff_t)self);
282 }
283
284 ReadWriteLock_AcquireWrite(&self->lock);
285
286 for (;;)
287 {
288 /* Wait for all the latches to empty. */
289 oldMask = *master;
290 if ((oldMask & MASTER_MASK) == 0)
291 return;
292
293 CondLock_Wait((ptrdiff_t)self, master, oldMask, CONDLOCK_DEFAULT_SPINCOUNT);
294 }
295 krisbash 1.1 }
296
297 void CachedLock_ReleaseRead(
298 _Inout_ CachedLock* self,
299 _In_ void* token
300 )
301 {
302 ptrdiff_t* latch = (ptrdiff_t*)token;
303 ptrdiff_t state;
304
305 if (latch == NULL)
306 {
307 /* This thread acquired the central lock, not a latch. */
308 ReadWriteLock_ReleaseRead(&self->lock);
309 return;
310 }
311
312 /* Decrement the same latch that got incremented before. */
313 state = Atomic_Dec(latch);
314 if (state == 0 && self->master != 0)
315 ClearCPU(self, latch);
316 krisbash 1.1 }
317
318 void CachedLock_ReleaseWrite(
319 _Inout_ CachedLock* self
320 )
321 {
322 ReadWriteLock_ReleaseWrite(&self->lock);
323
324 /* Revert the increment that happened during Acquire. */
325 Atomic_Add(&self->master, -MASTER_INCREMENT);
326 }
|