Pretty print.
[kopensolaris-gnu/glibc.git] / linuxthreads / spinlock.c
1 /* Linuxthreads - a simple clone()-based implementation of Posix        */
2 /* threads for Linux.                                                   */
3 /* Copyright (C) 1998 Xavier Leroy (Xavier.Leroy@inria.fr)              */
4 /*                                                                      */
5 /* This program is free software; you can redistribute it and/or        */
6 /* modify it under the terms of the GNU Library General Public License  */
7 /* as published by the Free Software Foundation; either version 2       */
8 /* of the License, or (at your option) any later version.               */
9 /*                                                                      */
10 /* This program 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        */
13 /* GNU Library General Public License for more details.                 */
14
15 /* Internal locks */
16
17 #include <errno.h>
18 #include <sched.h>
19 #include <time.h>
20 #include <stdlib.h>
21 #include <limits.h>
22 #include "pthread.h"
23 #include "internals.h"
24 #include "spinlock.h"
25 #include "restart.h"
26
27 /* The status field of a spinlock has the following meaning:
28      0: spinlock is free
29      1: spinlock is taken, no thread is waiting on it
30   ADDR: psinlock is taken, ADDR is address of thread descriptor for
31         first waiting thread, other waiting threads are linked via
32         their p_nextlock field.
33    The waiting list is not sorted by priority order.
34    Actually, we always insert at top of list (sole insertion mode
35    that can be performed without locking).
36    For __pthread_unlock, we perform a linear search in the list
37    to find the highest-priority, oldest waiting thread.
38    This is safe because there are no concurrent __pthread_unlock
39    operations -- only the thread that locked the mutex can unlock it. */
40
41 void internal_function __pthread_lock(struct _pthread_fastlock * lock,
42                                       pthread_descr self)
43 {
44   long oldstatus, newstatus;
45   int spurious_wakeup_count = 0;
46
47   do {
48     oldstatus = lock->__status;
49     if (oldstatus == 0) {
50       newstatus = 1;
51     } else {
52       if (self == NULL)
53         self = thread_self();
54       newstatus = (long) self;
55     }
56     if (self != NULL) {
57       THREAD_SETMEM(self, p_nextlock, (pthread_descr) oldstatus);
58       /* Make sure the store in p_nextlock completes before performing
59          the compare-and-swap */
60       MEMORY_BARRIER();
61     }
62   } while(! compare_and_swap(&lock->__status, oldstatus, newstatus,
63                              &lock->__spinlock));
64
65   /* Suspend with guard against spurious wakeup.
66      This can happen in pthread_cond_timedwait_relative, when the thread
67      wakes up due to timeout and is still on the condvar queue, and then
68      locks the queue to remove itself. At that point it may still be on the
69      queue, and may be resumed by a condition signal. */
70
71   if (oldstatus != 0) {
72     for (;;) {
73       suspend(self);
74       if (self->p_nextlock != NULL) {
75         /* Count resumes that don't belong to us. */
76         spurious_wakeup_count++;
77         continue;
78       }
79       break;
80     }
81   }
82
83   /* Put back any resumes we caught that don't belong to us. */
84   while (spurious_wakeup_count--)
85     restart(self);
86 }
87
88 int __pthread_unlock(struct _pthread_fastlock * lock)
89 {
90   long oldstatus;
91   pthread_descr thr, * ptr, * maxptr;
92   int maxprio;
93
94 again:
95   oldstatus = lock->__status;
96   if (oldstatus == 0 || oldstatus == 1) {
97     /* No threads are waiting for this lock.  Please note that we also
98        enter this case if the lock is not taken at all.  If this wouldn't
99        be done here we would crash further down.  */
100     if (! compare_and_swap_with_release_semantics (&lock->__status,
101                                                    oldstatus, 0,
102                                                    &lock->__spinlock))
103       goto again;
104     return 0;
105   }
106   /* Find thread in waiting queue with maximal priority */
107   ptr = (pthread_descr *) &lock->__status;
108   thr = (pthread_descr) oldstatus;
109   maxprio = 0;
110   maxptr = ptr;
111   while (thr != (pthread_descr) 1) {
112     if (thr->p_priority >= maxprio) {
113       maxptr = ptr;
114       maxprio = thr->p_priority;
115     }
116     ptr = &(thr->p_nextlock);
117     /* Prevent reordering of the load of lock->__status above and the
118        load of *ptr below, as well as reordering of *ptr between
119        several iterations of the while loop.  Some processors (e.g.
120        multiprocessor Alphas) could perform such reordering even though
121        the loads are dependent. */
122     READ_MEMORY_BARRIER();
123     thr = *ptr;
124   }
125   /* Prevent reordering of the load of lock->__status above and
126      thr->p_nextlock below */
127   READ_MEMORY_BARRIER();
128   /* Remove max prio thread from waiting list. */
129   if (maxptr == (pthread_descr *) &lock->__status) {
130     /* If max prio thread is at head, remove it with compare-and-swap
131        to guard against concurrent lock operation */
132     thr = (pthread_descr) oldstatus;
133     if (! compare_and_swap_with_release_semantics
134             (&lock->__status, oldstatus, (long)(thr->p_nextlock),
135              &lock->__spinlock))
136       goto again;
137   } else {
138     /* No risk of concurrent access, remove max prio thread normally */
139     thr = *maxptr;
140     *maxptr = thr->p_nextlock;
141   }
142   /* Prevent reordering of store to *maxptr above and store to thr->p_nextlock
143      below */
144   WRITE_MEMORY_BARRIER();
145   /* Wake up the selected waiting thread */
146   thr->p_nextlock = NULL;
147   restart(thr);
148
149   return 0;
150 }
151
152 /*
153  * Alternate fastlocks do not queue threads directly. Instead, they queue
154  * these wait queue node structures. When a timed wait wakes up due to
155  * a timeout, it can leave its wait node in the queue (because there
156  * is no safe way to remove from the quue). Some other thread will
157  * deallocate the abandoned node.
158  */
159
160
161 struct wait_node {
162   struct wait_node *next;       /* Next node in null terminated linked list */
163   pthread_descr thr;            /* The thread waiting with this node */
164   int abandoned;                /* Atomic flag */
165 };
166
167 static long wait_node_free_list;
168 static int wait_node_free_list_spinlock;
169
170 /* Allocate a new node from the head of the free list using an atomic
171    operation, or else using malloc if that list is empty.  A fundamental
172    assumption here is that we can safely access wait_node_free_list->next.
173    That's because we never free nodes once we allocate them, so a pointer to a
174    node remains valid indefinitely. */
175
176 static struct wait_node *wait_node_alloc(void)
177 {
178   long oldvalue, newvalue;
179
180   do {
181     oldvalue = wait_node_free_list;
182
183     if (oldvalue == 0)
184       return malloc(sizeof *wait_node_alloc());
185
186     newvalue = (long) ((struct wait_node *) oldvalue)->next;
187     WRITE_MEMORY_BARRIER();
188   } while (! compare_and_swap(&wait_node_free_list, oldvalue, newvalue,
189                               &wait_node_free_list_spinlock));
190
191   return (struct wait_node *) oldvalue;
192 }
193
194 /* Return a node to the head of the free list using an atomic
195    operation. */
196
197 static void wait_node_free(struct wait_node *wn)
198 {
199   long oldvalue, newvalue;
200
201   do {
202     oldvalue = wait_node_free_list;
203     wn->next = (struct wait_node *) oldvalue;
204     newvalue = (long) wn;
205     WRITE_MEMORY_BARRIER();
206   } while (! compare_and_swap(&wait_node_free_list, oldvalue, newvalue,
207                               &wait_node_free_list_spinlock));
208 }
209
210 /* Remove a wait node from the specified queue.  It is assumed
211    that the removal takes place concurrently with only atomic insertions at the
212    head of the queue. */
213
214 static void wait_node_dequeue(struct wait_node **pp_head,
215                               struct wait_node **pp_node,
216                               struct wait_node *p_node,
217                               int *spinlock)
218 {
219   long oldvalue, newvalue;
220
221   /* If the node is being deleted from the head of the
222      list, it must be deleted using atomic compare-and-swap.
223      Otherwise it can be deleted in the straightforward way. */
224
225   if (pp_node == pp_head) {
226     oldvalue = (long) p_node;
227     newvalue = (long) p_node->next;
228
229     if (compare_and_swap((long *) pp_node, oldvalue, newvalue, spinlock))
230       return;
231
232     /* Oops! Compare and swap failed, which means the node is
233        no longer first. We delete it using the ordinary method.  But we don't
234        know the identity of the node which now holds the pointer to the node
235        being deleted, so we must search from the beginning. */
236
237     for (pp_node = pp_head; *pp_node != p_node; pp_node = &(*pp_node)->next)
238       ; /* null body */
239   }
240
241   *pp_node = p_node->next;
242   return;
243 }
244
245 void __pthread_alt_lock(struct _pthread_fastlock * lock,
246                         pthread_descr self)
247 {
248   struct wait_node wait_node;
249   long oldstatus, newstatus;
250
251   do {
252     oldstatus = lock->__status;
253     if (oldstatus == 0) {
254       newstatus = 1;
255     } else {
256       if (self == NULL)
257         wait_node.thr = self = thread_self();
258       newstatus = (long) &wait_node;
259     }
260     wait_node.abandoned = 0;
261     wait_node.next = (struct wait_node *) oldstatus;
262     /* Make sure the store in wait_node.next completes before performing
263        the compare-and-swap */
264     MEMORY_BARRIER();
265   } while(! compare_and_swap(&lock->__status, oldstatus, newstatus,
266                              &lock->__spinlock));
267
268   /* Suspend. Note that unlike in __pthread_lock, we don't worry
269      here about spurious wakeup. That's because this lock is not
270      used in situations where that can happen; the restart can
271      only come from the previous lock owner. */
272
273   if (oldstatus != 0)
274     suspend(self);
275 }
276
277 /* Timed-out lock operation; returns 0 to indicate timeout. */
278
279 int __pthread_alt_timedlock(struct _pthread_fastlock * lock,
280                             pthread_descr self, const struct timespec *abstime)
281 {
282   struct wait_node *p_wait_node = wait_node_alloc();
283   long oldstatus, newstatus;
284
285   /* Out of memory, just give up and do ordinary lock. */
286   if (p_wait_node == 0) {
287     __pthread_alt_lock(lock, self);
288     return 1;
289   }
290
291   do {
292     oldstatus = lock->__status;
293     if (oldstatus == 0) {
294       newstatus = 1;
295     } else {
296       if (self == NULL)
297         p_wait_node->thr = self = thread_self();
298       newstatus = (long) p_wait_node;
299     }
300     p_wait_node->abandoned = 0;
301     p_wait_node->next = (struct wait_node *) oldstatus;
302     /* Make sure the store in wait_node.next completes before performing
303        the compare-and-swap */
304     MEMORY_BARRIER();
305   } while(! compare_and_swap(&lock->__status, oldstatus, newstatus,
306                              &lock->__spinlock));
307
308   /* If we did not get the lock, do a timed suspend. If we wake up due
309      to a timeout, then there is a race; the old lock owner may try
310      to remove us from the queue. This race is resolved by us and the owner
311      doing an atomic testandset() to change the state of the wait node from 0
312      to 1. If we succeed, then it's a timeout and we abandon the node in the
313      queue. If we fail, it means the owner gave us the lock. */
314
315   if (oldstatus != 0) {
316     if (timedsuspend(self, abstime) == 0) {
317       if (!testandset(&p_wait_node->abandoned))
318         return 0; /* Timeout! */
319
320       /* Eat oustanding resume from owner, otherwise wait_node_free() below
321          will race with owner's wait_node_dequeue(). */
322       suspend(self);
323     }
324   }
325
326   wait_node_free(p_wait_node);
327
328   return 1; /* Got the lock! */
329 }
330
331 void __pthread_alt_unlock(struct _pthread_fastlock *lock)
332 {
333   long oldstatus;
334   struct wait_node *p_node, **pp_node, *p_max_prio, **pp_max_prio;
335   struct wait_node ** const pp_head = (struct wait_node **) &lock->__status;
336   int maxprio;
337
338   while (1) {
339
340   /* If no threads are waiting for this lock, try to just
341      atomically release it. */
342
343     oldstatus = lock->__status;
344     if (oldstatus == 0 || oldstatus == 1) {
345       if (compare_and_swap_with_release_semantics (&lock->__status, oldstatus,
346                                                    0, &lock->__spinlock))
347         return;
348       else
349         continue;
350     }
351
352     /* Process the entire queue of wait nodes. Remove all abandoned
353        wait nodes and put them into the global free queue, and
354        remember the one unabandoned node which refers to the thread
355        having the highest priority. */
356
357     pp_max_prio = pp_node = pp_head;
358     p_max_prio = p_node = *pp_head;
359     maxprio = INT_MIN;
360
361     while (p_node != (struct wait_node *) 1) {
362       int prio;
363
364       if (p_node->abandoned) {
365         /* Remove abandoned node. */
366         wait_node_dequeue(pp_head, pp_node, p_node, &lock->__spinlock);
367         wait_node_free(p_node);
368         READ_MEMORY_BARRIER();
369         p_node = *pp_node;
370         continue;
371       } else if ((prio = p_node->thr->p_priority) >= maxprio) {
372         /* Otherwise remember it if its thread has a higher or equal priority
373            compared to that of any node seen thus far. */
374         maxprio = prio;
375         pp_max_prio = pp_node;
376         p_max_prio = p_node;
377       }
378
379       pp_node = &p_node->next;
380       READ_MEMORY_BARRIER();
381       p_node = *pp_node;
382     }
383
384     READ_MEMORY_BARRIER();
385
386     /* If all threads abandoned, go back to top */
387     if (maxprio == INT_MIN)
388       continue;
389
390     ASSERT (p_max_prio != (struct wait_node *) 1);
391
392     /* Now we want to to remove the max priority thread's wait node from
393        the list. Before we can do this, we must atomically try to change the
394        node's abandon state from zero to nonzero. If we succeed, that means we
395        have the node that we will wake up. If we failed, then it means the
396        thread timed out and abandoned the node in which case we repeat the
397        whole unlock operation. */
398
399     if (!testandset(&p_max_prio->abandoned)) {
400       wait_node_dequeue(pp_head, pp_max_prio, p_max_prio, &lock->__spinlock);
401       WRITE_MEMORY_BARRIER();
402       restart(p_max_prio->thr);
403       return;
404     }
405   }
406 }
407
408
409 /* Compare-and-swap emulation with a spinlock */
410
411 #ifdef TEST_FOR_COMPARE_AND_SWAP
412 int __pthread_has_cas = 0;
413 #endif
414
415 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
416
417 static void __pthread_acquire(int * spinlock);
418
419 int __pthread_compare_and_swap(long * ptr, long oldval, long newval,
420                                int * spinlock)
421 {
422   int res;
423   if (testandset(spinlock)) __pthread_acquire(spinlock);
424   if (*ptr == oldval) {
425     *ptr = newval; res = 1;
426   } else {
427     res = 0;
428   }
429   /* Prevent reordering of store to *ptr above and store to *spinlock below */
430   WRITE_MEMORY_BARRIER();
431   *spinlock = 0;
432   return res;
433 }
434
435 /* This function is called if the inlined test-and-set
436    in __pthread_compare_and_swap() failed */
437
438 /* The retry strategy is as follows:
439    - We test and set the spinlock MAX_SPIN_COUNT times, calling
440      sched_yield() each time.  This gives ample opportunity for other
441      threads with priority >= our priority to make progress and
442      release the spinlock.
443    - If a thread with priority < our priority owns the spinlock,
444      calling sched_yield() repeatedly is useless, since we're preventing
445      the owning thread from making progress and releasing the spinlock.
446      So, after MAX_SPIN_LOCK attemps, we suspend the calling thread
447      using nanosleep().  This again should give time to the owning thread
448      for releasing the spinlock.
449      Notice that the nanosleep() interval must not be too small,
450      since the kernel does busy-waiting for short intervals in a realtime
451      process (!).  The smallest duration that guarantees thread
452      suspension is currently 2ms.
453    - When nanosleep() returns, we try again, doing MAX_SPIN_COUNT
454      sched_yield(), then sleeping again if needed. */
455
456 static void __pthread_acquire(int * spinlock)
457 {
458   int cnt = 0;
459   struct timespec tm;
460
461   while (testandset(spinlock)) {
462     if (cnt < MAX_SPIN_COUNT) {
463       sched_yield();
464       cnt++;
465     } else {
466       tm.tv_sec = 0;
467       tm.tv_nsec = SPIN_SLEEP_DURATION;
468       nanosleep(&tm, NULL);
469       cnt = 0;
470     }
471   }
472 }
473
474 #endif