Merge remote branch 'gvdb/master'
[platform/upstream/glib.git] / glib / gbitlock.c
1 /*
2  * Copyright © 2008 Ryan Lortie
3  * Copyright © 2010 Codethink Limited
4  *
5  * This library is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU Lesser General Public
7  * License as published by the Free Software Foundation; either
8  * version 2 of the licence, or (at your option) any later version.
9  *
10  * This library is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13  * Lesser General Public License for more details.
14  *
15  * You should have received a copy of the GNU Lesser General Public
16  * License along with this library; if not, write to the
17  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18  * Boston, MA 02111-1307, USA.
19  *
20  * Author: Ryan Lortie <desrt@desrt.ca>
21  */
22
23 #include "gbitlock.h"
24
25 #include <glib/gatomic.h>
26 #include <glib/gslist.h>
27 #include <glib/gthread.h>
28
29 #include "gthreadprivate.h"
30 #include "config.h"
31
32
33 #ifdef G_BIT_LOCK_FORCE_FUTEX_EMULATION
34 #undef HAVE_FUTEX
35 #endif
36
37 #ifndef HAVE_FUTEX
38 static GSList *g_futex_address_list = NULL;
39 static GMutex *g_futex_mutex = NULL;
40 #endif
41
42 void
43 _g_futex_thread_init (void) {
44 #ifndef HAVE_FUTEX
45   g_futex_mutex = g_mutex_new ();
46 #endif
47 }
48
49 #ifdef HAVE_FUTEX
50 /*
51  * We have headers for futex(2) on the build machine.  This does not
52  * imply that every system that ever runs the resulting glib will have
53  * kernel support for futex, but you'd have to have a pretty old
54  * kernel in order for that not to be the case.
55  *
56  * If anyone actually gets bit by this, please file a bug. :)
57  */
58 #include <linux/futex.h>
59 #include <syscall.h>
60 #include <unistd.h>
61
62 /* < private >
63  * g_futex_wait:
64  * @address: a pointer to an integer
65  * @value: the value that should be at @address
66  *
67  * Atomically checks that the value stored at @address is equal to
68  * @value and then blocks.  If the value stored at @address is not
69  * equal to @value then this function returns immediately.
70  *
71  * To unblock, call g_futex_wake() on @address.
72  *
73  * This call may spuriously unblock (for example, in response to the
74  * process receiving a signal) but this is not guaranteed.  Unlike the
75  * Linux system call of a similar name, there is no guarantee that a
76  * waiting process will unblock due to a g_futex_wake() call in a
77  * separate process.
78  */
79 static void
80 g_futex_wait (const volatile gint *address,
81               gint                 value)
82 {
83   syscall (SYS_futex, address, (gsize) FUTEX_WAIT, (gsize) value, NULL);
84 }
85
86 /* < private >
87  * g_futex_wake:
88  * @address: a pointer to an integer
89  *
90  * Nominally, wakes one thread that is blocked in g_futex_wait() on
91  * @address (if any thread is currently waiting).
92  *
93  * As mentioned in the documention for g_futex_wait(), spurious
94  * wakeups may occur.  As such, this call may result in more than one
95  * thread being woken up.
96  */
97 static void
98 g_futex_wake (const volatile gint *address)
99 {
100   syscall (SYS_futex, address, (gsize) FUTEX_WAKE, (gsize) 1, NULL);
101 }
102
103 #else
104
105 /* emulate futex(2) */
106 typedef struct
107 {
108   const volatile gint *address;
109   gint                 ref_count;
110   GCond               *wait_queue;
111 } WaitAddress;
112
113 static WaitAddress *
114 g_futex_find_address (const volatile gint *address)
115 {
116   GSList *node;
117
118   for (node = g_futex_address_list; node; node = node->next)
119     {
120       WaitAddress *waiter = node->data;
121
122       if (waiter->address == address)
123         return waiter;
124     }
125
126   return NULL;
127 }
128
129 static void
130 g_futex_wait (const volatile gint *address,
131               gint                 value)
132 {
133   g_mutex_lock (g_futex_mutex);
134   if G_LIKELY (g_atomic_int_get (address) == value)
135     {
136       WaitAddress *waiter;
137
138       if ((waiter = g_futex_find_address (address)) == NULL)
139         {
140           waiter = g_slice_new (WaitAddress);
141           waiter->address = address;
142           waiter->wait_queue = g_cond_new ();
143           waiter->ref_count = 0;
144           g_futex_address_list =
145             g_slist_prepend (g_futex_address_list, waiter);
146         }
147
148       waiter->ref_count++;
149       g_cond_wait (waiter->wait_queue, g_futex_mutex);
150
151       if (!--waiter->ref_count)
152         {
153           g_futex_address_list =
154             g_slist_remove (g_futex_address_list, waiter);
155           g_cond_free (waiter->wait_queue);
156           g_slice_free (WaitAddress, waiter);
157         }
158     }
159   g_mutex_unlock (g_futex_mutex);
160 }
161
162 static void
163 g_futex_wake (const volatile gint *address)
164 {
165   WaitAddress *waiter;
166
167   /* need to lock here for two reasons:
168    *   1) need to acquire/release lock to ensure waiter is not in
169    *      the process of registering a wait
170    *   2) need to -stay- locked until the end to ensure a wake()
171    *      in another thread doesn't cause 'waiter' to stop existing
172    */
173   g_mutex_lock (g_futex_mutex);
174   if ((waiter = g_futex_find_address (address)))
175     g_cond_signal (waiter->wait_queue);
176   g_mutex_unlock (g_futex_mutex);
177 }
178 #endif
179
180 #define CONTENTION_CLASSES 11
181 static volatile gint g_bit_lock_contended[CONTENTION_CLASSES];
182
183 /**
184  * g_bit_lock:
185  * @address: a pointer to an integer
186  * @lock_bit: a bit value between 0 and 31
187  *
188  * Sets the indicated @lock_bit in @address.  If the bit is already
189  * set, this call will block until g_bit_unlock() unsets the
190  * corresponding bit.
191  *
192  * Attempting to lock on two different bits within the same integer is
193  * not supported and will very probably cause deadlocks.
194  *
195  * The value of the bit that is set is (1u << @bit).  If @bit is not
196  * between 0 and 31 then the result is undefined.
197  *
198  * This function accesses @address atomically.  All other accesses to
199  * @address must be atomic in order for this function to work
200  * reliably.
201  *
202  * Since: 2.24
203  **/
204 void
205 g_bit_lock (volatile gint *address,
206             gint           lock_bit)
207 {
208   guint v;
209
210  retry:
211   v = g_atomic_int_get (address);
212   if (v & (1u << lock_bit))
213     /* already locked */
214     {
215       guint class = ((gsize) address) % G_N_ELEMENTS (g_bit_lock_contended);
216
217       g_atomic_int_add (&g_bit_lock_contended[class], +1);
218       g_futex_wait (address, v);
219       g_atomic_int_add (&g_bit_lock_contended[class], -1);
220
221       goto retry;
222     }
223
224   if (!g_atomic_int_compare_and_exchange (address, v, v | (1u << lock_bit)))
225     goto retry;
226 }
227
228 /**
229  * g_bit_trylock:
230  * @address: a pointer to an integer
231  * @lock_bit: a bit value between 0 and 31
232  * @returns: %TRUE if the lock was acquired
233  *
234  * Sets the indicated @lock_bit in @address, returning %TRUE if
235  * successful.  If the bit is already set, returns %FALSE immediately.
236  *
237  * Attempting to lock on two different bits within the same integer is
238  * not supported.
239  *
240  * The value of the bit that is set is (1u << @bit).  If @bit is not
241  * between 0 and 31 then the result is undefined.
242  *
243  * This function accesses @address atomically.  All other accesses to
244  * @address must be atomic in order for this function to work
245  * reliably.
246  *
247  * Since: 2.24
248  **/
249 gboolean
250 g_bit_trylock (volatile gint *address,
251                gint           lock_bit)
252 {
253   guint v;
254
255  retry:
256   v = g_atomic_int_get (address);
257   if (v & (1u << lock_bit))
258     /* already locked */
259     return FALSE;
260
261   if (!g_atomic_int_compare_and_exchange (address, v, v | (1u << lock_bit)))
262     goto retry;
263
264   return TRUE;
265 }
266
267 /**
268  * g_bit_unlock:
269  * @address: a pointer to an integer
270  * @lock_bit: a bit value between 0 and 31
271  *
272  * Clears the indicated @lock_bit in @address.  If another thread is
273  * currently blocked in g_bit_lock() on this same bit then it will be
274  * woken up.
275  *
276  * This function accesses @address atomically.  All other accesses to
277  * @address must be atomic in order for this function to work
278  * reliably.
279  *
280  * Since: 2.24
281  **/
282 void
283 g_bit_unlock (volatile gint *address,
284               gint           lock_bit)
285 {
286   guint class = ((gsize) address) % G_N_ELEMENTS (g_bit_lock_contended);
287   guint v;
288
289  retry:
290   v = g_atomic_int_get (address);
291   if (!g_atomic_int_compare_and_exchange (address, v, v & ~(1u << lock_bit)))
292     goto retry;
293
294   if (g_atomic_int_get (&g_bit_lock_contended[class]))
295     g_futex_wake (address);
296 }