1 /*
2 * ptw32_OLL_lock.c
3 *
4 * Description:
5 * This translation unit implements extended reader/writer queue-based locks.
6 *
7 * --------------------------------------------------------------------------
8 *
9 * Pthreads-win32 - POSIX Threads Library for Win32
10 * Copyright(C) 1998 John E. Bossom
11 * Copyright(C) 1999,2005 Pthreads-win32 contributors
12 *
13 * Contact Email: rpj@callisto.canberra.edu.au
14 *
15 * The current list of contributors is contained
16 * in the file CONTRIBUTORS included with the source
17 * code distribution. The list can also be seen at the
18 * following World Wide Web location:
19 * http://sources.redhat.com/pthreads-win32/contributors.html
20 *
21 * This library is free software; you can redistribute it and/or
22 * modify it under the terms of the GNU Lesser General Public
23 * License as published by the Free Software Foundation; either
24 * version 2 of the License, or (at your option) any later version.
25 *
26 * This library is distributed in the hope that it will be useful,
27 * but WITHOUT ANY WARRANTY; without even the implied warranty of
28 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
29 * Lesser General Public License for more details.
30 *
31 * You should have received a copy of the GNU Lesser General Public
32 * License along with this library in the file COPYING.LIB;
33 * if not, write to the Free Software Foundation, Inc.,
34 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
35 */
36
37 /*
38 * About the OLL lock (Scalable Reader-Writer Lock):
39 *
40 * OLL locks are queue-based locks similar to the MCS queue lock, where the queue
41 * nodes are local to the thread but where reader threads can enter the critical
42 * section immediately without going through a central guard lock if there are
43 * already readers holding the lock.
44 *
45 * Covered by United States Patent Application 20100241774 (Oracle)
46 */
47
48 #include "pthread.h"
49 #include "sched.h"
50 #include "implement.h"
51
52 /*
53 * C-SNZI support
54 */
55 typedef union ptw32_oll_counter_t_ ptw32_oll_counter_t;
56 typedef struct ptw32_oll_snziRoot_t_ ptw32_oll_snziRoot_t;
57 typedef struct ptw32_oll_snziNode_t_ ptw32_oll_snziNode_t;
58 typedef union ptw32_oll_snziNodeOrRoot_t_ ptw32_oll_snziNodeOrRoot_t;
59 typedef struct ptw32_oll_queryResult_t_ ptw32_oll_queryResult_t;
60 typedef struct ptw32_oll_ticket_t_ ptw32_oll_ticket_t;
61 typedef struct ptw32_oll_csnzi_t_ ptw32_oll_csnzi_t;
62
63 enum
64 {
65 ptw32_archWidth = sizeof(size_t)*8,
66 ptw32_oll_countWidth = ptw32_archWidth-2
67 };
68
69 #define PTW32_OLL_MAXREADERS (((size_t)2<<(ptw32_oll_countWidth-1))-1)
70
71 union ptw32_oll_counter_t_
72 {
73 size_t word : ptw32_archWidth;
74 struct
75 {
76 /*
77 * This needs to be a single word
78 *
79 * ------------------------------------
80 * | STATE | ROOT | COUNT (readers) |
81 * ------------------------------------
82 * 63 / 31 62 / 30 61 / 29 .. 0
83 */
84 size_t count : ptw32_oll_countWidth;
85 size_t root : 1; /* ROOT or NODE */
86 size_t state : 1; /* OPEN or CLOSED (root only) */
87 } internal;
88 };
89
90 struct ptw32_oll_snziRoot_t_
91 {
92 /*
93 * "counter" must be at same offset in both
94 * ptw32_oll_snziNode_t and ptw32_oll_snziRoot_t
95 */
96 ptw32_oll_counter_t counter;
97 };
98
99 enum
100 {
101 ptw32_oll_snziRoot_open = 0,
102 ptw32_oll_snziRoot_closed = 1
103 };
104
105 enum
106 {
107 ptw32_oll_snzi_root = 0,
108 ptw32_oll_snzi_node = 1
109 };
110
111 /*
112 * Some common SNZI root whole-word states that can be used to set or compare
113 * root words with a single operation.
114 */
115 ptw32_oll_snziRoot_t ptw32_oll_snziRoot_openAndZero = {.counter.internal.count = 0,
116 .counter.internal.root = ptw32_oll_snzi_root,
117 .counter.internal.state = ptw32_oll_snziRoot_open};
118 ptw32_oll_snziRoot_t ptw32_oll_snziRoot_closedAndZero = {.counter.internal.count = 0,
119 .counter.internal.root = ptw32_oll_snzi_root,
120 .counter.internal.state = ptw32_oll_snziRoot_closed};
121
122 struct ptw32_oll_queryResult_t_
123 {
124 BOOL nonZero;
125 BOOL open;
126 };
127
128 union ptw32_oll_snziNodeOrRoot_t_
129 {
130 ptw32_oll_snziRoot_t* rootPtr;
131 ptw32_oll_snziNode_t* nodePtr;
132 };
133
134 struct ptw32_oll_snziNode_t_
135 {
136 /* "counter" must be at same offset in both
137 * ptw32_oll_snziNode_t and ptw32_oll_snziRoot_t
138 */
139 ptw32_oll_counter_t counter;
140 ptw32_oll_snziNodeOrRoot_t parentPtr;
141 };
142
143 struct ptw32_oll_ticket_t_
144 {
145 ptw32_oll_snziNodeOrRoot_t snziNodeOrRoot;
146 };
147
148 ptw32_oll_ticket_t ptw32_oll_ticket_null = {NULL};
149
150 struct ptw32_oll_csnzi_t_
151 {
152 ptw32_oll_snziRoot_t proxyRoot;
153 ptw32_oll_snziNode_t leafs[];
154 };
155
156 /*
157 * FOLL lock support
158 */
159
160 typedef struct ptw32_foll_node_t_ ptw32_foll_node_t;
161 typedef struct ptw32_foll_local_t_ ptw32_foll_local_t;
162 typedef struct ptw32_foll_rwlock_t_ ptw32_foll_rwlock_t;
163
164 enum
165 {
166 ptw32_srwl_reader,
167 ptw32_srwl_writer
168 };
169
170 enum
171 {
172 ptw32_srwl_free,
173 ptw32_srwl_in_use
174 };
175
176 struct ptw32_foll_node_t_
177 {
178 ptw32_foll_node_t* qNextPtr;
179 ptw32_oll_csnzi_t* csnziPtr;
180 ptw32_foll_node_t* nextPtr;
181 int kind;
182 int allocState;
183 BOOL spin;
184 };
185
186 struct ptw32_foll_local_t_
187 {
188 ptw32_foll_node_t* rNodePtr; // Default read node. Immutable
189 ptw32_foll_node_t* wNodePtr; // Write node. Immutable.
190 ptw32_foll_node_t* departFromPtr; // List node we last arrived at.
191 ptw32_oll_ticket_t ticket; // C-SNZI ticket
192 };
193
194 struct ptw32_foll_rwlock_t_
195 {
196 ptw32_foll_node_t* tailPtr;
197 ptw32_foll_node_t* rNodesPtr; // Head of reader node
198 };
199
200 /*
201 * ShouldArriveAtTree() returns true if:
202 * the compare_exchange in Arrive() fails too often under read access; or
203 * ??
204 * Note that this is measured across all access to
205 * this lock, not just this attempt, so that highly
206 * read-contended locks will use C-SNZI. Lightly
207 * read-contended locks can reduce memory usage and some
208 * processing by using the root directly.
209 */
210 BOOL
ptw32_oll_ShouldArriveAtTree()211 ptw32_oll_ShouldArriveAtTree()
212 {
213 return PTW32_FALSE;
214 }
215
216 size_t
ptw32_oll_GetLeafForThread()217 ptw32_oll_GetLeafForThread()
218 {
219 return 0;
220 }
221
222 /*
223 * Only readers call ptw32_oll_Arrive()
224 *
225 * Checks whether the C-SNZI state is OPEN, and if so,
226 * increments the surplus of the C-SNZI by either directly
227 * arriving at the root node, or calling TreeArrive on one
228 * of the leaf nodes. Returns a ticket pointing to the node
229 * that was arrived at. If the state is CLOSED, makes no
230 * change and returns a ticket that contains no pointer.
231 */
232 ptw32_oll_ticket_t
ptw32_oll_Arrive(ptw32_oll_csnzi_t * csnzi)233 ptw32_oll_Arrive(ptw32_oll_csnzi_t* csnzi)
234 {
235 for (;;)
236 {
237 ptw32_oll_ticket_t ticket;
238 ptw32_oll_snziRoot_t oldProxy = csnzi->proxyRoot;
239 if (oldProxy.counter.internal.state != ptw32_oll_snziRoot_open)
240 {
241 ticket.snziNodeOrRoot.rootPtr = (ptw32_oll_snziRoot_t*)NULL;
242 return ticket;
243 }
244 if (!ptw32_oll_ShouldArriveAtTree())
245 {
246 ptw32_oll_snziRoot_t newProxy = oldProxy;
247 newProxy.counter.internal.count++;
248 if (PTW32_INTERLOCKED_COMPARE_EXCHANGE_SIZE(
249 (PTW32_INTERLOCKED_SIZEPTR)&csnzi->proxyRoot.counter,
250 (PTW32_INTERLOCKED_SIZE)newProxy.counter.word,
251 (PTW32_INTERLOCKED_SIZE)oldProxy.counter.word)
252 == (PTW32_INTERLOCKED_SIZE)oldProxy.counter.word)
253 {
254 /* Exchange successful */
255 ticket.snziNodeOrRoot.rootPtr = &csnzi->proxyRoot;
256 return ticket;
257 }
258 }
259 else
260 {
261 ptw32_oll_snziNode_t* leafPtr = &csnzi->leafs[ptw32_oll_GetLeafForThread()];
262 ticket.snziNodeOrRoot.nodePtr = (ptw32_oll_TreeArrive(leafPtr) ? leafPtr : (ptw32_oll_snziNode_t*)NULL);
263 return ticket;
264 }
265 }
266 }
267
268 /*
269 * Decrements the C-SNZI surplus. Returns false iff the
270 * resulting state is CLOSED and the surplus is zero.
271 * Ticket must have been returned by an arrival. Must have
272 * received this ticket from Arrive more times than Depart
273 * has been called with the ticket. (Thus, the surplus
274 * must be greater than zero.)
275 */
276 BOOL
ptw32_oll_Depart(ptw32_oll_ticket_t ticket)277 ptw32_oll_Depart(ptw32_oll_ticket_t ticket)
278 {
279 return ptw32_oll_TreeDepart(ticket.snziNodeOrRoot);
280 }
281
282 /*
283 * Increments the C-SNZI surplus and returns true if the
284 * C-SNZI is open or has a surplus. Calls TreeArrive
285 * recursively on the node’s parent if needed.
286 * Otherwise, returns false without making any changes.
287 */
288 BOOL
ptw32_oll_TreeArrive(ptw32_oll_snziNodeOrRoot_t snziNodeOrRoot)289 ptw32_oll_TreeArrive(ptw32_oll_snziNodeOrRoot_t snziNodeOrRoot)
290 {
291 if (snziNodeOrRoot.nodePtr->counter.internal.root != ptw32_oll_snzi_root)
292 {
293 /* Non-root node */
294 ptw32_oll_counter_t newCounter, oldCounter;
295 BOOL arrivedAtParent = PTW32_FALSE;
296 do
297 {
298 oldCounter = snziNodeOrRoot.nodePtr->counter;
299 if (0 == oldCounter.internal.count && !arrivedAtParent)
300 {
301 if (ptw32_oll_TreeArrive(snziNodeOrRoot.nodePtr->parentPtr))
302 arrivedAtParent = PTW32_TRUE;
303 else
304 return PTW32_FALSE;
305 }
306 newCounter = oldCounter;
307 newCounter.internal.count++;
308 } while (PTW32_INTERLOCKED_COMPARE_EXCHANGE_SIZE(
309 (PTW32_INTERLOCKED_SIZEPTR)&snziNodeOrRoot.nodePtr->counter,
310 (PTW32_INTERLOCKED_SIZE)newCounter.word,
311 (PTW32_INTERLOCKED_SIZE)oldCounter.word)
312 != (PTW32_INTERLOCKED_SIZE)oldCounter.word);
313 if (newCounter.internal.count != 0 && arrivedAtParent)
314 ptw32_oll_TreeDepart(snziNodeOrRoot.nodePtr->parentPtr);
315 return PTW32_TRUE;
316 }
317 else
318 {
319 /* Root node */
320 ptw32_oll_snziRoot_t newRoot, oldRoot;
321 do
322 {
323 oldRoot = *(ptw32_oll_snziRoot_t*)snziNodeOrRoot.rootPtr;
324 if (oldRoot.counter.word == ptw32_oll_snziRoot_closedAndZero.counter.word)
325 return PTW32_FALSE;
326 newRoot = oldRoot;
327 newRoot.counter.internal.count++;
328 } while (PTW32_INTERLOCKED_COMPARE_EXCHANGE_SIZE(
329 (PTW32_INTERLOCKED_SIZEPTR)&snziNodeOrRoot.rootPtr->counter,
330 (PTW32_INTERLOCKED_SIZE)newRoot.counter.word,
331 (PTW32_INTERLOCKED_SIZE)oldRoot.counter.word)
332 != (PTW32_INTERLOCKED_SIZE)oldRoot.counter.word);
333 return PTW32_TRUE;
334 }
335 }
336
337 /*
338 * Decrements the C-SNZI surplus, calling TreeDepart
339 * recursively on the node’s parent if needed. Returns
340 * false iff the resulting state of the C-SNZI is CLOSED
341 * and the surplus is zero. Otherwise, returns true.
342 */
343 BOOL
ptw32_oll_TreeDepart(ptw32_oll_snziNodeOrRoot_t snziNodeOrRoot)344 ptw32_oll_TreeDepart(ptw32_oll_snziNodeOrRoot_t snziNodeOrRoot)
345 {
346 if (snziNodeOrRoot.nodePtr->counter.internal.root != ptw32_oll_snzi_root)
347 {
348 /* Non-root node */
349 ptw32_oll_counter_t newCounter, oldCounter;
350 do
351 {
352 newCounter = oldCounter = snziNodeOrRoot.nodePtr->counter;
353 newCounter.internal.count--;
354 } while (PTW32_INTERLOCKED_COMPARE_EXCHANGE_SIZE(
355 (PTW32_INTERLOCKED_SIZEPTR)&snziNodeOrRoot.nodePtr->counter,
356 (PTW32_INTERLOCKED_SIZE)newCounter.word,
357 (PTW32_INTERLOCKED_SIZE)oldCounter.word)
358 != (PTW32_INTERLOCKED_SIZE)oldCounter.word);
359 return (0 == newCounter.internal.count)
360 ? ptw32_oll_TreeDepart(snziNodeOrRoot.nodePtr->parentPtr)
361 : PTW32_TRUE;
362 }
363 else
364 {
365 /* Root node */
366 ptw32_oll_snziRoot_t newRoot, oldRoot;
367 do
368 {
369 newRoot = oldRoot = *(ptw32_oll_snziRoot_t*)snziNodeOrRoot.rootPtr;
370 newRoot.counter.internal.count--;
371 } while (PTW32_INTERLOCKED_COMPARE_EXCHANGE_SIZE(
372 (PTW32_INTERLOCKED_SIZEPTR)&snziNodeOrRoot.rootPtr->counter,
373 (PTW32_INTERLOCKED_SIZE)newRoot.counter.word,
374 (PTW32_INTERLOCKED_SIZE)oldRoot.counter.word)
375 != (PTW32_INTERLOCKED_SIZE)oldRoot.counter.word);
376 return (newRoot.counter.word != ptw32_oll_snziRoot_closedAndZero.counter.word);
377 }
378 }
379
380 /*
381 * Opens a C-SNZI object. Requires C-SNZI state to be
382 * CLOSED and the surplus to be zero.
383 */
384 void
ptw32_oll_Open(ptw32_oll_csnzi_t * csnziPtr)385 ptw32_oll_Open(ptw32_oll_csnzi_t* csnziPtr)
386 {
387 csnziPtr->proxyRoot = ptw32_oll_snziRoot_openAndZero;
388 }
389
390 /*
391 * Opens a C-SNZI object while atomically performing count
392 * arrivals. Requires C-SNZI state to be CLOSED and
393 * the surplus to be zero.
394 */
395 void
ptw32_oll_OpenWithArrivals(ptw32_oll_csnzi_t * csnziPtr,size_t count,BOOL close)396 ptw32_oll_OpenWithArrivals(ptw32_oll_csnzi_t* csnziPtr, size_t count, BOOL close)
397 {
398 csnziPtr->proxyRoot.counter.internal.count = count;
399 csnziPtr->proxyRoot.counter.internal.state = (close ? ptw32_oll_snziRoot_closed : ptw32_oll_snziRoot_open);
400 }
401
402 /*
403 * Closes a C-SNZI object. Returns true iff the C-SNZI
404 * state changed from OPEN to CLOSED and the surplus is
405 * zero.
406 */
407 BOOL
ptw32_oll_Close(ptw32_oll_csnzi_t * csnziPtr)408 ptw32_oll_Close(ptw32_oll_csnzi_t* csnziPtr)
409 {
410 ptw32_oll_snziRoot_t newProxy, oldProxy;
411 do
412 {
413 oldProxy = csnziPtr->proxyRoot;
414 if (oldProxy.counter.internal.state != ptw32_oll_snziRoot_open)
415 {
416 return PTW32_FALSE;
417 }
418 newProxy = oldProxy;
419 newProxy.counter.internal.state = ptw32_oll_snziRoot_closed;
420 } while (PTW32_INTERLOCKED_COMPARE_EXCHANGE_SIZE(
421 (PTW32_INTERLOCKED_SIZEPTR)&csnziPtr->proxyRoot.counter,
422 (PTW32_INTERLOCKED_SIZE)newProxy.counter.word,
423 (PTW32_INTERLOCKED_SIZE)oldProxy.counter.word)
424 != (PTW32_INTERLOCKED_SIZE)oldProxy.counter.word);
425 return (newProxy.counter.word == ptw32_oll_snziRoot_closedAndZero.counter.word);
426 }
427
428 /*
429 * Closes a C-SNZI if its surplus is zero. Otherwise, does
430 * nothing. Returns true iff C-SNZI state changed from
431 * OPEN to CLOSED.
432 */
433 BOOL
ptw32_oll_CloseIfEmpty(ptw32_oll_csnzi_t * csnziPtr)434 ptw32_oll_CloseIfEmpty(ptw32_oll_csnzi_t* csnziPtr)
435 {
436 ptw32_oll_snziRoot_t newProxy, oldProxy;
437 do
438 {
439 oldProxy = csnziPtr->proxyRoot;
440 if (oldProxy.counter.word != ptw32_oll_snziRoot_openAndZero.counter.word)
441 {
442 return PTW32_FALSE;
443 }
444 newProxy = ptw32_oll_snziRoot_closedAndZero;
445 } while (PTW32_INTERLOCKED_COMPARE_EXCHANGE_SIZE(
446 (PTW32_INTERLOCKED_SIZEPTR)&csnziPtr->proxyRoot.counter,
447 (PTW32_INTERLOCKED_SIZE)newProxy.counter.word,
448 (PTW32_INTERLOCKED_SIZE)oldProxy.counter.word)
449 != (PTW32_INTERLOCKED_SIZE)oldProxy.counter.word);
450 return PTW32_TRUE;
451 }
452
453 /*
454 * Returns whether the C-SNZI has a nonzero surplus and
455 * whether the C-SNZI is open.
456 * "nonZero" doesn't appear to be used anywhere in the algorithms.
457 */
458 ptw32_oll_queryResult_t
ptw32_oll_Query(ptw32_oll_csnzi_t * csnziPtr)459 ptw32_oll_Query(ptw32_oll_csnzi_t* csnziPtr)
460 {
461 ptw32_oll_queryResult_t query;
462 ptw32_oll_snziRoot_t proxy = csnziPtr->proxyRoot;
463
464 query.nonZero = (proxy.counter.internal.count > 0);
465 query.open = (proxy.counter.internal.state == ptw32_oll_snziRoot_open);
466 return query;
467 }
468
469 /*
470 * Returns whether the Arrive operation that returned
471 * the ticket succeeded.
472 */
473 BOOL
ptw32_oll_Arrived(ptw32_oll_ticket_t t)474 ptw32_oll_Arrived(ptw32_oll_ticket_t t)
475 {
476 return (t.snziNodeOrRoot.nodePtr != NULL);
477 }
478
479 /*
480 * Constructs and returns a ticket that can be used to
481 * depart from the root node.
482 */
483 ptw32_oll_ticket_t
ptw32_oll_DirectTicket(ptw32_oll_csnzi_t * csnziPtr)484 ptw32_oll_DirectTicket(ptw32_oll_csnzi_t* csnziPtr)
485 {
486 ptw32_oll_ticket_t ticket;
487 ticket.snziNodeOrRoot.rootPtr = &csnziPtr->proxyRoot;
488 return ticket;
489 }
490
491 /* Scalable RW Locks */
492
493 typedef struct ptw32_srwl_rwlock_t_ ptw32_srwl_rwlock_t;
494 typedef struct ptw32_srwl_node_t_ ptw32_srwl_node_t;
495 typedef struct ptw32_srwl_local_t_ ptw32_srwl_local_t;
496
497 enum
498 {
499 ptw32_srwl_reader = 0,
500 ptw32_srwl_writer = 1
501 };
502
503 enum
504 {
505 ptw32_srwl_free = 0,
506 ptw32_srwl_in_use = 1
507 };
508
509 struct ptw32_srwl_rwlock_t_
510 {
511 ptw32_srwl_node_t* tailPtr;
512 ptw32_srwl_node_t* readerNodePtr;
513 };
514
515 struct ptw32_srwl_node_t_
516 {
517 ptw32_srwl_node_t* qNextPtr;
518 ptw32_oll_csnzi_t* csnziPtr;
519 ptw32_srwl_node_t* nextReaderPtr;
520 int kind; /* ptw32_srwl_reader, ptw32_srwl_writer */
521 int allocState; /* ptw32_srwl_free, ptw32_srwl_in_use */
522 BOOL spin;
523 };
524
525 /*
526 * When a ptw32_srwl_local_t is instantiated the "kind" of each of
527 * rNode and wNode must be set as appropriate. This is the only
528 * time "kind" is set.
529 */
530 struct ptw32_srwl_local_t_
531 {
532 ptw32_srwl_node_t* rNodePtr;
533 ptw32_srwl_node_t* wNodePtr;
534 ptw32_srwl_node_t* departFromPtr;
535 ptw32_oll_ticket_t ticket;
536 };
537
538 /* Allocates a new reader node. */
539 ptw32_srwl_node_t*
ptw32_srwl_AllocReaderNode(ptw32_srwl_local_t * local)540 ptw32_srwl_AllocReaderNode(ptw32_srwl_local_t* local)
541 {
542 ptw32_srwl_node_t* currNodePtr = local->rNodePtr;
543 for (;;)
544 {
545 if (currNodePtr->allocState == ptw32_srwl_free)
546 {
547 if (PTW32_INTERLOCKED_COMPARE_EXCHANGE_LONG(
548 (PTW32_INTERLOCKED_LONGPTR)&currNodePtr->allocState,
549 (PTW32_INTERLOCKED_LONG)ptw32_srwl_in_use,
550 (PTW32_INTERLOCKED_LONG)ptw32_srwl_free)
551 == (PTW32_INTERLOCKED_LONG)ptw32_srwl_in_use)
552 {
553 return currNodePtr;
554 }
555 }
556 currNodePtr = currNodePtr->next;
557 }
558 }
559
560 /*
561 * Frees a reader node. Requires that its allocState
562 * is ptw32_srwl_in_use.
563 */
564 void
ptw32_srwl_FreeReaderNode(ptw32_srwl_node_t * nodePtr)565 ptw32_srwl_FreeReaderNode(ptw32_srwl_node_t* nodePtr)
566 {
567 nodePtr->allocState := ptw32_srwl_free;
568 }
569
570 void
ptw32_srwl_WriterLock(ptw32_srwl_rwlock_t * lockPtr,ptw32_srwl_local_t * localPtr)571 ptw32_srwl_WriterLock(ptw32_srwl_rwlock_t* lockPtr, ptw32_srwl_local_t* localPtr)
572 {
573 oldTailPtr = (ptw32_srwl_rwlock_t*)PTW32_INTERLOCKED_EXCHANGE_PTR(
574 (PTW32_INTERLOCKED_PVOID_PTR)&lockPtr->tailPtr,
575 (PTW32_INTERLOCKED_PVOID)localPtr->wNodePtr);
576 if (oldTailPtr != NULL)
577 {
578 localPtr->wNodePtr->spin := PTW32_TRUE;
579 oldTailPtr->qNextPtr = localPtr->wNodePtr;
580 if (oldTailPtr->kind == ptw32_srwl_writer)
581 {
582 while (localPtr->wNodePtr->spin);
583 }
584 else
585 {
586 /* Wait until node is properly recycled */
587 while (ptw32_oll_Query(oldTailPtr->csnzi).open);
588 /*
589 * Close C-SNZI of previous reader node.
590 * If there are no readers to signal us, spin on
591 * previous node and free it before entering
592 * critical section.
593 */
594 if (ptw32_oll_Close(oldTailPtr->csnzi))
595 {
596 while (oldTailPtr->spin);
597 ptw32_srwl_FreeReaderNode(oldTailPtr);
598 }
599 else
600 {
601 while (localPtr->wNodePtr->spin);
602 }
603 }
604 }
605 }
606
607 void
ptw32_srwl_WriterUnlock(ptw32_srwl_rwlock_t * lockPtr,ptw32_srwl_local_t * localPtr)608 ptw32_srwl_WriterUnlock(ptw32_srwl_rwlock_t* lockPtr, ptw32_srwl_local_t* localPtr)
609 {
610 if (localPtr->wNodePtr->qNextPtr == NULL)
611 {
612 if (PTW32_INTERLOCKED_COMPARE_EXCHANGE_PTR(
613 (PTW32_INTERLOCKED_PVOIDPTR)&lockPtr->tailPtr,
614 (PTW32_INTERLOCKED_PVOID)NULL,
615 (PTW32_INTERLOCKED_PVOID)localPtr->wNodePtr)
616 == (PTW32_INTERLOCKED_PVOID)NULL)
617 {
618 return;
619 }
620 else
621 {
622 while (localPtr->wNodePtr->qNextPtr == NULL);
623 }
624 }
625 /* Clean up */
626 localPtr->wNodePtr->qNextPtr->spin = PTW32_FALSE;
627 localPtr->wNodePtr->qNextPtr = NULL;
628 }
629
630 void
ptw32_srwl_ReaderLock(ptw32_srwl_rwlock_t * lockPtr,ptw32_srwl_local_t * localPtr)631 ptw32_srwl_ReaderLock(ptw32_srwl_rwlock_t* lockPtr, ptw32_srwl_local_t* localPtr)
632 {
633 ptw32_srwl_node_t* rNodePtr = NULL;
634 for (;;)
635 {
636 ptw32_srwl_node_t* tailPtr = lockPtr->tailPtr;
637 /* If no nodes are in the queue */
638 if (tailPtr == NULL)
639 {
640 if (rNodePtr == NULL)
641 {
642 rNodePtr = ptw32_srwl_AllocReaderNode(localPtr);
643 }
644 rNodePtr->spin = PTW32_FALSE;
645 if (PTW32_INTERLOCKED_COMPARE_EXCHANGE_PTR(
646 (PTW32_INTERLOCKED_PVOIDPTR)&lockPtr->tailPtr,
647 (PTW32_INTERLOCKED_PVOID)rNodePtr,
648 (PTW32_INTERLOCKED_PVOID)NULL)
649 == (PTW32_INTERLOCKED_PVOID)rNodePtr)
650 {
651 ptw32_oll_Open(rNodePtr->csnzi);
652 localPtr->ticket = ptw32_oll_Arrive(rNodePtr->csnzi);
653 if (ptw32_oll_Arrived(localPtr->ticket))
654 {
655 localPtr->departFromPtr = rNodePtr;
656 return;
657 }
658 /* Avoid reusing inserted node */
659 rNodePtr = NULL;
660 }
661 }
662 /* Otherwise, there is a node in the queue */
663 else
664 {
665 /* Is last node a writer node? */
666 if (tailPtr->kind == ptw32_srwl_writer)
667 {
668 if (rNodePtr == NULL)
669 {
670 rNodePtr = ptw32_srwl_AllocReaderNode(localPtr);
671 }
672 rNodePtr->spin = PTW32_TRUE;
673 if (PTW32_INTERLOCKED_COMPARE_EXCHANGE_PTR(
674 (PTW32_INTERLOCKED_PVOIDPTR)&lockPtr->tailPtr,
675 (PTW32_INTERLOCKED_PVOID)rNodePtr,
676 (PTW32_INTERLOCKED_PVOID)tailPtr)
677 == (PTW32_INTERLOCKED_PVOID)rNodePtr)
678 {
679 tailPtr->qNextPtr = rNodePtr;
680 localPtr->ticket = ptw32_oll_Arrive(rNodePtr->csnzi);
681 if (ptw32_oll_Arrived(localPtr->ticket))
682 {
683 localPtr->departFromPtr = rNodePtr;
684 while (rNodePtr->spin);
685 return;
686 }
687 /* Avoid reusing inserted node */
688 rNodePtr = NULL;
689 }
690 }
691 /*
692 * Otherwise, last node is a reader node.
693 * (tailPtr->kind == ptw32_srwl_reader)
694 */
695 else
696 {
697 localPtr->ticket = ptw32_oll_Arrive(tailPtr->csnzi);
698 if (ptw32_oll_Arrived(localPtr->ticket))
699 {
700 if (rNodePtr != NULL)
701 {
702 ptw32_srwl_FreeReaderNode(rNodePtr);
703 }
704 localPtr->departFromPtr = tailPtr;
705 while (tailPtr->spin);
706 return;
707 }
708 }
709 }
710 }
711 }
712
713 void
ptw32_srwl_ReaderUnlock(ptw32_srwl_rwlock_t * lockPtr,ptw32_srwl_local_t * localPtr)714 ptw32_srwl_ReaderUnlock(ptw32_srwl_rwlock_t* lockPtr, ptw32_srwl_local_t* localPtr)
715 {
716 if (ptw32_oll_Depart(localPtr->departFromPtr->csnzi, localPtr->ticket))
717 {
718 return;
719 }
720 /* Clean up */
721 localPtr->departFromPtr->qNextPtr->spin = PTW32_FALSE;
722 localPtr->departFromPtr->qNextPtr = NULL;
723 ptw32_srwl_FreeReaderNode(localPtr->departFromPtr);
724 }
725
726
727 #include <stdio.h>
728
main()729 int main()
730 {
731 printf("%lx\n", PTW32_OLL_MAXREADERS);
732 return 0;
733 }
734
735