/[pcsx2_0.9.7]/trunk/3rdparty/w32pthreads/ptw32_MCS_lock.c
ViewVC logotype

Contents of /trunk/3rdparty/w32pthreads/ptw32_MCS_lock.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 280 - (show annotations) (download)
Thu Dec 23 12:02:12 2010 UTC (9 years, 1 month ago) by william
File MIME type: text/plain
File size: 6162 byte(s)
re-commit (had local access denied errors when committing)
1 /*
2 * ptw32_MCS_lock.c
3 *
4 * Description:
5 * This translation unit implements 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 * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
35 */
36
37 /*
38 * About MCS locks:
39 *
40 * MCS locks are queue-based locks, where the queue nodes are local to the
41 * thread. The 'lock' is nothing more than a global pointer that points to
42 * the last node in the queue, or is NULL if the queue is empty.
43 *
44 * Originally designed for use as spin locks requiring no kernel resources
45 * for synchronisation or blocking, the implementation below has adapted
46 * the MCS spin lock for use as a general mutex that will suspend threads
47 * when there is lock contention.
48 *
49 * Because the queue nodes are thread-local, most of the memory read/write
50 * operations required to add or remove nodes from the queue do not trigger
51 * cache-coherence updates.
52 *
53 * Like 'named' mutexes, MCS locks consume system resources transiently -
54 * they are able to acquire and free resources automatically - but MCS
55 * locks do not require any unique 'name' to identify the lock to all
56 * threads using it.
57 *
58 * Usage of MCS locks:
59 *
60 * - you need a global ptw32_mcs_lock_t instance initialised to 0 or NULL.
61 * - you need a local thread-scope ptw32_mcs_local_node_t instance, which
62 * may serve several different locks but you need at least one node for
63 * every lock held concurrently by a thread.
64 *
65 * E.g.:
66 *
67 * ptw32_mcs_lock_t lock1 = 0;
68 * ptw32_mcs_lock_t lock2 = 0;
69 *
70 * void *mythread(void *arg)
71 * {
72 * ptw32_mcs_local_node_t node;
73 *
74 * ptw32_mcs_acquire (&lock1, &node);
75 * ptw32_mcs_release (&node);
76 *
77 * ptw32_mcs_acquire (&lock2, &node);
78 * ptw32_mcs_release (&node);
79 * {
80 * ptw32_mcs_local_node_t nodex;
81 *
82 * ptw32_mcs_acquire (&lock1, &node);
83 * ptw32_mcs_acquire (&lock2, &nodex);
84 *
85 * ptw32_mcs_release (&nodex);
86 * ptw32_mcs_release (&node);
87 * }
88 * return (void *)0;
89 * }
90 */
91
92 #include "ptw32pch.h"
93
94 /*
95 * ptw32_mcs_flag_set -- notify another thread about an event.
96 *
97 * Set event if an event handle has been stored in the flag, and
98 * set flag to -1 otherwise. Note that -1 cannot be a valid handle value.
99 */
100 INLINE void
101 ptw32_mcs_flag_set (HANDLE * flag)
102 {
103 HANDLE e = (HANDLE)_InterlockedCompareExchangePointer(flag, (HANDLE)-1, (HANDLE)0);
104
105 if (e)
106 {
107 /* another thread has already stored an event handle in the flag */
108 SetEvent(e);
109 }
110 }
111
112 /*
113 * ptw32_mcs_flag_set -- wait for notification from another.
114 *
115 * Store an event handle in the flag and wait on it if the flag has not been
116 * set, and proceed without creating an event otherwise.
117 */
118 INLINE void
119 ptw32_mcs_flag_wait (HANDLE * flag)
120 {
121 if (0 == _InterlockedExchangeAddPointer(flag, NULL)) /* MBR fence */
122 {
123 /* the flag is not set. create event. */
124
125 HANDLE e = CreateEvent(NULL, PTW32_FALSE, PTW32_FALSE, NULL);
126
127 if (0 == _InterlockedCompareExchangePointer(flag, e, 0))
128 {
129 /* stored handle in the flag. wait on it now. */
130 WaitForSingleObject(e, INFINITE);
131 }
132
133 CloseHandle(e);
134 }
135 }
136
137 /*
138 * ptw32_mcs_lock_acquire -- acquire an MCS lock.
139 *
140 * See:
141 * J. M. Mellor-Crummey and M. L. Scott.
142 * Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors.
143 * ACM Transactions on Computer Systems, 9(1):21-65, Feb. 1991.
144 */
145 INLINE void
146 ptw32_mcs_lock_acquire (ptw32_mcs_lock_t * lock, ptw32_mcs_local_node_t * node)
147 {
148 ptw32_mcs_local_node_t *pred;
149
150 node->lock = lock;
151 node->nextFlag = 0;
152 node->readyFlag = 0;
153 node->next = 0; /* initially, no successor */
154
155 /* queue for the lock */
156 pred = (ptw32_mcs_local_node_t *)_InterlockedExchangePointer(lock, node);
157
158 if (0 != pred)
159 {
160 /* the lock was not free. link behind predecessor. */
161 pred->next = node;
162 ptw32_mcs_flag_set(&pred->nextFlag);
163 ptw32_mcs_flag_wait(&node->readyFlag);
164 }
165 }
166
167 /*
168 * ptw32_mcs_lock_release -- release an MCS lock.
169 *
170 * See:
171 * J. M. Mellor-Crummey and M. L. Scott.
172 * Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors.
173 * ACM Transactions on Computer Systems, 9(1):21-65, Feb. 1991.
174 */
175 INLINE void
176 ptw32_mcs_lock_release (ptw32_mcs_local_node_t * node)
177 {
178 ptw32_mcs_lock_t *lock = node->lock;
179 ptw32_mcs_local_node_t *next = (ptw32_mcs_local_node_t *)
180 InterlockedExchangeAdd((LPLONG)&node->next, 0); /* MBR fence */
181
182 if (0 == next)
183 {
184 /* no known successor */
185
186 if (node == (ptw32_mcs_local_node_t *)
187 _InterlockedCompareExchangePointer(lock, 0, node))
188 {
189 /* no successor, lock is free now */
190 return;
191 }
192
193 /* wait for successor */
194 ptw32_mcs_flag_wait(&node->nextFlag);
195 next = (ptw32_mcs_local_node_t *)
196 _InterlockedExchangeAddPointer(&node->next, NULL); /* MBR fence */
197 }
198
199 /* pass the lock */
200 ptw32_mcs_flag_set(&next->readyFlag);
201 }

  ViewVC Help
Powered by ViewVC 1.1.22