WebSVN – HelenOS-historic – Diff – /uspace/trunk/libc/generic/futex.c


/*
 * Copyright (C) 2006 Jakub Jermar
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * - Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 * - The name of the author may not be used to endorse or promote products
 *   derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 /** @addtogroup libc
 * @{
 */
/** @file
 */
 
#include <futex.h>
#include <atomic.h>
#include <libc.h>
#include <stdio.h>
#include <types.h>
#include <kernel/synch/synch.h>
 
/*
 * Note about race conditions.
 * Because of non-atomic nature of operations performed sequentially on the futex
 * counter and the futex wait queue, there is a race condition:
 *
 * (wq->missed_wakeups == 1) && (futex->count = 1)
 *
 * Scenario 1 (wait queue timeout vs. futex_up()):
 * 1. assume wq->missed_wakeups == 0 && futex->count == -1
 *    (ie. thread A sleeping, thread B in the critical section)
 * 2. A receives timeout and gets removed from the wait queue
 * 3. B wants to leave the critical section and calls futex_up()
 * 4. B thus changes futex->count from -1 to 0
 * 5. B has to call SYS_FUTEX_WAKEUP syscall to wake up the sleeping thread
 * 6. B finds the wait queue empty and changes wq->missed_wakeups from 0 to 1
 * 7. A fixes futex->count (i.e. the number of waiting threads) by changing it from 0 to 1
 *
 * Scenario 2 (conditional down operation vs. futex_up)
 * 1. assume wq->missed_wakeups == 0 && futex->count == 0
 *    (i.e. thread A is in the critical section)
 * 2. thread B performs futex_trydown() operation and changes futex->count from 0 to -1
 *    B is now obliged to call SYS_FUTEX_SLEEP syscall
 * 3. A wants to leave the critical section and does futex_up()
 * 4. A thus changes futex->count from -1 to 0 and must call SYS_FUTEX_WAKEUP syscall
 * 5. B finds the wait queue empty and immediatelly aborts the conditional sleep
 * 6. No thread is queueing in the wait queue so wq->missed_wakeups changes from 0 to 1
 * 6. B fixes futex->count (i.e. the number of waiting threads) by changing it from 0 to 1
 *
 * Both scenarios allow two threads to be in the critical section simultaneously.
 * One without kernel intervention and the other through wq->missed_wakeups being 1.
 *
 * To mitigate this problem, futex_down_timeout() detects that the syscall didn't sleep
 * in the wait queue, fixes the futex counter and RETRIES the whole operation again.
 *
 */
 
/** Initialize futex counter.
 *
 * @param futex Futex.
 * @param val Initialization value.
 */
void futex_initialize(atomic_t *futex, int val)
{
    atomic_set(futex, val);
}
 
int futex_down(atomic_t *futex)
{
    return futex_down_timeout(futex, SYNCH_NO_TIMEOUT, SYNCH_FLAGS_NONE);
}
 
int futex_trydown(atomic_t *futex)
{
    return futex_down_timeout(futex, SYNCH_NO_TIMEOUT, SYNCH_FLAGS_NON_BLOCKING);
}
 
/** Try to down the futex.
 *
 * @param futex Futex.
 * @param usec Microseconds to wait. Zero value means sleep without timeout.
 * @param flags Select mode of operation. See comment for waitq_sleep_timeout().
 *
 * @return ENOENT if there is no such virtual address. One of ESYNCH_OK_ATOMIC
 *     and ESYNCH_OK_BLOCKED on success or ESYNCH_TIMEOUT if the lock was
 *     not acquired because of a timeout or ESYNCH_WOULD_BLOCK if the
 *     operation could not be carried out atomically (if requested so).
 */
int futex_down_timeout(atomic_t *futex, uint32_t usec, int flags)
{
    int rc;
   
    while (atomic_predec(futex) < 0) {
        rc = __SYSCALL3(SYS_FUTEX_SLEEP, (sysarg_t) &futex->count, (sysarg_t) usec, (sysarg_t) flags);
       
        switch (rc) {
        case ESYNCH_OK_ATOMIC:
            /*
             * Because of a race condition between timeout and futex_up()
             * and between conditional futex_down_timeout() and futex_up(),
             * we have to give up and try again in this special case.
             */
            atomic_inc(futex);
            break;
 
        case ESYNCH_TIMEOUT:
            atomic_inc(futex);
            return ESYNCH_TIMEOUT;
            break;
 
        case ESYNCH_WOULD_BLOCK:
            /*
             * The conditional down operation should be implemented this way.
             * The userspace-only variant tends to accumulate missed wakeups
             * in the kernel futex wait queue.
             */
            atomic_inc(futex);
            return ESYNCH_WOULD_BLOCK;
            break;
 
        case ESYNCH_OK_BLOCKED:
            /*
             * Enter the critical section.
             * The futex counter has already been incremented for us.
             */
            return ESYNCH_OK_BLOCKED;
            break;
        default:
            return rc;
        }
    }
 
    /*
     * Enter the critical section.
     */
    return ESYNCH_OK_ATOMIC;
}
 
/** Up the futex.
 *
 * @param futex Futex.
 *
 * @return ENOENT if there is no such virtual address. Otherwise zero.
 */
int futex_up(atomic_t *futex)
{
    long val;
   
    val = atomic_postinc(futex);
    if (val < 0)
        return __SYSCALL1(SYS_FUTEX_WAKEUP, (sysarg_t) &futex->count);
       
    return 0;
}
 
 
 /** @}
 */
 
 
 

Subversion Repositories HelenOS-historic

(root)/uspace/trunk/libc/generic/futex.c – Rev 1503 → 1653

Rev 1503		Rev 1653
1	/*	1	/*
2	* Copyright (C) 2006 Jakub Jermar	2	* Copyright (C) 2006 Jakub Jermar
3	* All rights reserved.	3	* All rights reserved.
4	*	4	*
5	* Redistribution and use in source and binary forms, with or without	5	* Redistribution and use in source and binary forms, with or without
6	* modification, are permitted provided that the following conditions	6	* modification, are permitted provided that the following conditions
7	* are met:	7	* are met:
8	*	8	*
9	* - Redistributions of source code must retain the above copyright	9	* - Redistributions of source code must retain the above copyright
10	* notice, this list of conditions and the following disclaimer.	10	* notice, this list of conditions and the following disclaimer.
11	* - Redistributions in binary form must reproduce the above copyright	11	* - Redistributions in binary form must reproduce the above copyright
12	* notice, this list of conditions and the following disclaimer in the	12	* notice, this list of conditions and the following disclaimer in the
13	* documentation and/or other materials provided with the distribution.	13	* documentation and/or other materials provided with the distribution.
14	* - The name of the author may not be used to endorse or promote products	14	* - The name of the author may not be used to endorse or promote products
15	* derived from this software without specific prior written permission.	15	* derived from this software without specific prior written permission.
16	*	16	*
17	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR	17	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18	* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES	18	* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.	19	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,	20	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT	21	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22	* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,	22	* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY	23	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT	24	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF	25	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.	26	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-		27	*/
-		28
-		29	/** @addtogroup libc
-		30	* @{
-		31	*/
-		32	/** @file
27	*/	33	*/
28		34
29	#include <futex.h>	35	#include <futex.h>
30	#include <atomic.h>	36	#include <atomic.h>
31	#include <libc.h>	37	#include <libc.h>
32	#include <stdio.h>	38	#include <stdio.h>
33	#include <types.h>	39	#include <types.h>
34	#include <kernel/synch/synch.h>	40	#include <kernel/synch/synch.h>
35		41
36	/*	42	/*
37	* Note about race conditions.	43	* Note about race conditions.
38	* Because of non-atomic nature of operations performed sequentially on the futex	44	* Because of non-atomic nature of operations performed sequentially on the futex
39	* counter and the futex wait queue, there is a race condition:	45	* counter and the futex wait queue, there is a race condition:
40	*	46	*
41	* (wq->missed_wakeups == 1) && (futex->count = 1)	47	* (wq->missed_wakeups == 1) && (futex->count = 1)
42	*	48	*
43	* Scenario 1 (wait queue timeout vs. futex_up()):	49	* Scenario 1 (wait queue timeout vs. futex_up()):
44	* 1. assume wq->missed_wakeups == 0 && futex->count == -1	50	* 1. assume wq->missed_wakeups == 0 && futex->count == -1
45	* (ie. thread A sleeping, thread B in the critical section)	51	* (ie. thread A sleeping, thread B in the critical section)
46	* 2. A receives timeout and gets removed from the wait queue	52	* 2. A receives timeout and gets removed from the wait queue
47	* 3. B wants to leave the critical section and calls futex_up()	53	* 3. B wants to leave the critical section and calls futex_up()
48	* 4. B thus changes futex->count from -1 to 0	54	* 4. B thus changes futex->count from -1 to 0
49	* 5. B has to call SYS_FUTEX_WAKEUP syscall to wake up the sleeping thread	55	* 5. B has to call SYS_FUTEX_WAKEUP syscall to wake up the sleeping thread
50	* 6. B finds the wait queue empty and changes wq->missed_wakeups from 0 to 1	56	* 6. B finds the wait queue empty and changes wq->missed_wakeups from 0 to 1
51	* 7. A fixes futex->count (i.e. the number of waiting threads) by changing it from 0 to 1	57	* 7. A fixes futex->count (i.e. the number of waiting threads) by changing it from 0 to 1
52	*	58	*
53	* Scenario 2 (conditional down operation vs. futex_up)	59	* Scenario 2 (conditional down operation vs. futex_up)
54	* 1. assume wq->missed_wakeups == 0 && futex->count == 0	60	* 1. assume wq->missed_wakeups == 0 && futex->count == 0
55	* (i.e. thread A is in the critical section)	61	* (i.e. thread A is in the critical section)
56	* 2. thread B performs futex_trydown() operation and changes futex->count from 0 to -1	62	* 2. thread B performs futex_trydown() operation and changes futex->count from 0 to -1
57	* B is now obliged to call SYS_FUTEX_SLEEP syscall	63	* B is now obliged to call SYS_FUTEX_SLEEP syscall
58	* 3. A wants to leave the critical section and does futex_up()	64	* 3. A wants to leave the critical section and does futex_up()
59	* 4. A thus changes futex->count from -1 to 0 and must call SYS_FUTEX_WAKEUP syscall	65	* 4. A thus changes futex->count from -1 to 0 and must call SYS_FUTEX_WAKEUP syscall
60	* 5. B finds the wait queue empty and immediatelly aborts the conditional sleep	66	* 5. B finds the wait queue empty and immediatelly aborts the conditional sleep
61	* 6. No thread is queueing in the wait queue so wq->missed_wakeups changes from 0 to 1	67	* 6. No thread is queueing in the wait queue so wq->missed_wakeups changes from 0 to 1
62	* 6. B fixes futex->count (i.e. the number of waiting threads) by changing it from 0 to 1	68	* 6. B fixes futex->count (i.e. the number of waiting threads) by changing it from 0 to 1
63	*	69	*
64	* Both scenarios allow two threads to be in the critical section simultaneously.	70	* Both scenarios allow two threads to be in the critical section simultaneously.
65	* One without kernel intervention and the other through wq->missed_wakeups being 1.	71	* One without kernel intervention and the other through wq->missed_wakeups being 1.
66	*	72	*
67	* To mitigate this problem, futex_down_timeout() detects that the syscall didn't sleep	73	* To mitigate this problem, futex_down_timeout() detects that the syscall didn't sleep
68	* in the wait queue, fixes the futex counter and RETRIES the whole operation again.	74	* in the wait queue, fixes the futex counter and RETRIES the whole operation again.
69	*	75	*
70	*/	76	*/
71		77
72	/** Initialize futex counter.	78	/** Initialize futex counter.
73	*	79	*
74	* @param futex Futex.	80	* @param futex Futex.
75	* @param val Initialization value.	81	* @param val Initialization value.
76	*/	82	*/
77	void futex_initialize(atomic_t *futex, int val)	83	void futex_initialize(atomic_t *futex, int val)
78	{	84	{
79	atomic_set(futex, val);	85	atomic_set(futex, val);
80	}	86	}
81		87
82	int futex_down(atomic_t *futex)	88	int futex_down(atomic_t *futex)
83	{	89	{
84	return futex_down_timeout(futex, SYNCH_NO_TIMEOUT, SYNCH_FLAGS_NONE);	90	return futex_down_timeout(futex, SYNCH_NO_TIMEOUT, SYNCH_FLAGS_NONE);
85	}	91	}
86		92
87	int futex_trydown(atomic_t *futex)	93	int futex_trydown(atomic_t *futex)
88	{	94	{
89	return futex_down_timeout(futex, SYNCH_NO_TIMEOUT, SYNCH_FLAGS_NON_BLOCKING);	95	return futex_down_timeout(futex, SYNCH_NO_TIMEOUT, SYNCH_FLAGS_NON_BLOCKING);
90	}	96	}
91		97
92	/** Try to down the futex.	98	/** Try to down the futex.
93	*	99	*
94	* @param futex Futex.	100	* @param futex Futex.
95	* @param usec Microseconds to wait. Zero value means sleep without timeout.	101	* @param usec Microseconds to wait. Zero value means sleep without timeout.
96	* @param flags Select mode of operation. See comment for waitq_sleep_timeout().	102	* @param flags Select mode of operation. See comment for waitq_sleep_timeout().
97	*	103	*
98	* @return ENOENT if there is no such virtual address. One of ESYNCH_OK_ATOMIC	104	* @return ENOENT if there is no such virtual address. One of ESYNCH_OK_ATOMIC
99	* and ESYNCH_OK_BLOCKED on success or ESYNCH_TIMEOUT if the lock was	105	* and ESYNCH_OK_BLOCKED on success or ESYNCH_TIMEOUT if the lock was
100	* not acquired because of a timeout or ESYNCH_WOULD_BLOCK if the	106	* not acquired because of a timeout or ESYNCH_WOULD_BLOCK if the
101	* operation could not be carried out atomically (if requested so).	107	* operation could not be carried out atomically (if requested so).
102	*/	108	*/
103	int futex_down_timeout(atomic_t *futex, uint32_t usec, int flags)	109	int futex_down_timeout(atomic_t *futex, uint32_t usec, int flags)
104	{	110	{
105	int rc;	111	int rc;
106		112
107	while (atomic_predec(futex) < 0) {	113	while (atomic_predec(futex) < 0) {
108	rc = __SYSCALL3(SYS_FUTEX_SLEEP, (sysarg_t) &futex->count, (sysarg_t) usec, (sysarg_t) flags);	114	rc = __SYSCALL3(SYS_FUTEX_SLEEP, (sysarg_t) &futex->count, (sysarg_t) usec, (sysarg_t) flags);
109		115
110	switch (rc) {	116	switch (rc) {
111	case ESYNCH_OK_ATOMIC:	117	case ESYNCH_OK_ATOMIC:
112	/*	118	/*
113	* Because of a race condition between timeout and futex_up()	119	* Because of a race condition between timeout and futex_up()
114	* and between conditional futex_down_timeout() and futex_up(),	120	* and between conditional futex_down_timeout() and futex_up(),
115	* we have to give up and try again in this special case.	121	* we have to give up and try again in this special case.
116	*/	122	*/
117	atomic_inc(futex);	123	atomic_inc(futex);
118	break;	124	break;
119		125
120	case ESYNCH_TIMEOUT:	126	case ESYNCH_TIMEOUT:
121	atomic_inc(futex);	127	atomic_inc(futex);
122	return ESYNCH_TIMEOUT;	128	return ESYNCH_TIMEOUT;
123	break;	129	break;
124		130
125	case ESYNCH_WOULD_BLOCK:	131	case ESYNCH_WOULD_BLOCK:
126	/*	132	/*
127	* The conditional down operation should be implemented this way.	133	* The conditional down operation should be implemented this way.
128	* The userspace-only variant tends to accumulate missed wakeups	134	* The userspace-only variant tends to accumulate missed wakeups
129	* in the kernel futex wait queue.	135	* in the kernel futex wait queue.
130	*/	136	*/
131	atomic_inc(futex);	137	atomic_inc(futex);
132	return ESYNCH_WOULD_BLOCK;	138	return ESYNCH_WOULD_BLOCK;
133	break;	139	break;
134		140
135	case ESYNCH_OK_BLOCKED:	141	case ESYNCH_OK_BLOCKED:
136	/*	142	/*
137	* Enter the critical section.	143	* Enter the critical section.
138	* The futex counter has already been incremented for us.	144	* The futex counter has already been incremented for us.
139	*/	145	*/
140	return ESYNCH_OK_BLOCKED;	146	return ESYNCH_OK_BLOCKED;
141	break;	147	break;
142	default:	148	default:
143	return rc;	149	return rc;
144	}	150	}
145	}	151	}
146		152
147	/*	153	/*
148	* Enter the critical section.	154	* Enter the critical section.
149	*/	155	*/
150	return ESYNCH_OK_ATOMIC;	156	return ESYNCH_OK_ATOMIC;
151	}	157	}
152		158
153	/** Up the futex.	159	/** Up the futex.
154	*	160	*
155	* @param futex Futex.	161	* @param futex Futex.
156	*	162	*
157	* @return ENOENT if there is no such virtual address. Otherwise zero.	163	* @return ENOENT if there is no such virtual address. Otherwise zero.
158	*/	164	*/
159	int futex_up(atomic_t *futex)	165	int futex_up(atomic_t *futex)
160	{	166	{
161	long val;	167	long val;
162		168
163	val = atomic_postinc(futex);	169	val = atomic_postinc(futex);
164	if (val < 0)	170	if (val < 0)
165	return __SYSCALL1(SYS_FUTEX_WAKEUP, (sysarg_t) &futex->count);	171	return __SYSCALL1(SYS_FUTEX_WAKEUP, (sysarg_t) &futex->count);
166		172
167	return 0;	173	return 0;
168	}	174	}
-		175
-		176
-		177	/** @}
-		178	*/
-		179
-		180
169		181