WebSVN – HelenOS – Diff – /branches/arm/uspace/lib/libc/generic/futex.c


/*
 * Copyright (c) 2008 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 <sys/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(futex_t *futex, int val)
{
    atomic_set(futex, val);
}
 
int futex_down(futex_t *futex)
{
    return futex_down_timeout(futex, SYNCH_NO_TIMEOUT, SYNCH_FLAGS_NONE);
}
 
int futex_trydown(futex_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(futex_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(futex_t *futex)
{
    long val;
   
    val = atomic_postinc(futex);
    if (val < 0)
        return __SYSCALL1(SYS_FUTEX_WAKEUP, (sysarg_t) &futex->count);
       
    return 0;
}
 
/** @}
 */
 

Rev 2682	Rev 3478
1	/*	1	/*
2	* Copyright (c) 2008 Jakub Jermar	2	* Copyright (c) 2008 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	*/	27	*/
28		28
29	/** @addtogroup libc	29	/** @addtogroup libc
30	* @{	30	* @{
31	*/	31	*/
32	/** @file	32	/** @file
33	*/	33	*/
34		34
35	#include <futex.h>	35	#include <futex.h>
36	#include <atomic.h>	36	#include <atomic.h>
37	#include <libc.h>	37	#include <libc.h>
38	#include <stdio.h>	38	#include <stdio.h>
39	#include <sys/types.h>	39	#include <sys/types.h>
40	#include <kernel/synch/synch.h>	40	#include <kernel/synch/synch.h>
41		41
42	/*	42	/*
43	* Note about race conditions.	43	* Note about race conditions.
44	* Because of non-atomic nature of operations performed sequentially on the	44	* Because of non-atomic nature of operations performed sequentially on the
45	* futex counter and the futex wait queue, there is a race condition:	45	* futex counter and the futex wait queue, there is a race condition:
46	*	46	*
47	* (wq->missed_wakeups == 1) && (futex->count = 1)	47	* (wq->missed_wakeups == 1) && (futex->count = 1)
48	*	48	*
49	* Scenario 1 (wait queue timeout vs. futex_up()):	49	* Scenario 1 (wait queue timeout vs. futex_up()):
50	* 1. assume wq->missed_wakeups == 0 && futex->count == -1	50	* 1. assume wq->missed_wakeups == 0 && futex->count == -1
51	* (ie. thread A sleeping, thread B in the critical section)	51	* (ie. thread A sleeping, thread B in the critical section)
52	* 2. A receives timeout and gets removed from the wait queue	52	* 2. A receives timeout and gets removed from the wait queue
53	* 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()
54	* 4. B thus changes futex->count from -1 to 0	54	* 4. B thus changes futex->count from -1 to 0
55	* 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
56	* 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
57	* 7. A fixes futex->count (i.e. the number of waiting threads) by changing it	57	* 7. A fixes futex->count (i.e. the number of waiting threads) by changing it
58	* from 0 to 1	58	* from 0 to 1
59	*	59	*
60	* Scenario 2 (conditional down operation vs. futex_up)	60	* Scenario 2 (conditional down operation vs. futex_up)
61	* 1. assume wq->missed_wakeups == 0 && futex->count == 0	61	* 1. assume wq->missed_wakeups == 0 && futex->count == 0
62	* (i.e. thread A is in the critical section)	62	* (i.e. thread A is in the critical section)
63	* 2. thread B performs futex_trydown() operation and changes futex->count from	63	* 2. thread B performs futex_trydown() operation and changes futex->count from
64	* 0 to -1	64	* 0 to -1
65	* B is now obliged to call SYS_FUTEX_SLEEP syscall	65	* B is now obliged to call SYS_FUTEX_SLEEP syscall
66	* 3. A wants to leave the critical section and does futex_up()	66	* 3. A wants to leave the critical section and does futex_up()
67	* 4. A thus changes futex->count from -1 to 0 and must call SYS_FUTEX_WAKEUP	67	* 4. A thus changes futex->count from -1 to 0 and must call SYS_FUTEX_WAKEUP
68	* syscall	68	* syscall
69	* 5. B finds the wait queue empty and immediatelly aborts the conditional sleep	69	* 5. B finds the wait queue empty and immediatelly aborts the conditional sleep
70	* 6. No thread is queueing in the wait queue so wq->missed_wakeups changes from	70	* 6. No thread is queueing in the wait queue so wq->missed_wakeups changes from
71	* 0 to 1	71	* 0 to 1
72	* 6. B fixes futex->count (i.e. the number of waiting threads) by changing it	72	* 6. B fixes futex->count (i.e. the number of waiting threads) by changing it
73	* from 0 to 1	73	* from 0 to 1
74	*	74	*
75	* Both scenarios allow two threads to be in the critical section	75	* Both scenarios allow two threads to be in the critical section
76	* simultaneously. One without kernel intervention and the other through	76	* simultaneously. One without kernel intervention and the other through
77	* wq->missed_wakeups being 1.	77	* wq->missed_wakeups being 1.
78	*	78	*
79	* To mitigate this problem, futex_down_timeout() detects that the syscall	79	* To mitigate this problem, futex_down_timeout() detects that the syscall
80	* didn't sleep in the wait queue, fixes the futex counter and RETRIES the	80	* didn't sleep in the wait queue, fixes the futex counter and RETRIES the
81	* whole operation again.	81	* whole operation again.
82	*/	82	*/
83		83
84	/** Initialize futex counter.	84	/** Initialize futex counter.
85	*	85	*
86	* @param futex Futex.	86	* @param futex Futex.
87	* @param val Initialization value.	87	* @param val Initialization value.
88	*/	88	*/
89	void futex_initialize(futex_t *futex, int val)	89	void futex_initialize(futex_t *futex, int val)
90	{	90	{
91	atomic_set(futex, val);	91	atomic_set(futex, val);
92	}	92	}
93		93
94	int futex_down(futex_t *futex)	94	int futex_down(futex_t *futex)
95	{	95	{
96	return futex_down_timeout(futex, SYNCH_NO_TIMEOUT, SYNCH_FLAGS_NONE);	96	return futex_down_timeout(futex, SYNCH_NO_TIMEOUT, SYNCH_FLAGS_NONE);
97	}	97	}
98		98
99	int futex_trydown(futex_t *futex)	99	int futex_trydown(futex_t *futex)
100	{	100	{
101	return futex_down_timeout(futex, SYNCH_NO_TIMEOUT,	101	return futex_down_timeout(futex, SYNCH_NO_TIMEOUT,
102	SYNCH_FLAGS_NON_BLOCKING);	102	SYNCH_FLAGS_NON_BLOCKING);
103	}	103	}
104		104
105	/** Try to down the futex.	105	/** Try to down the futex.
106	*	106	*
107	* @param futex Futex.	107	* @param futex Futex.
108	* @param usec Microseconds to wait. Zero value means sleep without	108	* @param usec Microseconds to wait. Zero value means sleep without
109	* timeout.	109	* timeout.
110	* @param flags Select mode of operation. See comment for	110	* @param flags Select mode of operation. See comment for
111	* waitq_sleep_timeout().	111	* waitq_sleep_timeout().
112	*	112	*
113	* @return ENOENT if there is no such virtual address. One of	113	* @return ENOENT if there is no such virtual address. One of
114	* ESYNCH_OK_ATOMIC and ESYNCH_OK_BLOCKED on success or	114	* ESYNCH_OK_ATOMIC and ESYNCH_OK_BLOCKED on success or
115	* ESYNCH_TIMEOUT if the lock was not acquired because of	115	* ESYNCH_TIMEOUT if the lock was not acquired because of
116	* a timeout or ESYNCH_WOULD_BLOCK if the operation could	116	* a timeout or ESYNCH_WOULD_BLOCK if the operation could
117	* not be carried out atomically (if requested so).	117	* not be carried out atomically (if requested so).
118	*/	118	*/
119	int futex_down_timeout(futex_t *futex, uint32_t usec, int flags)	119	int futex_down_timeout(futex_t *futex, uint32_t usec, int flags)
120	{	120	{
121	int rc;	121	int rc;
122		122
123	while (atomic_predec(futex) < 0) {	123	while (atomic_predec(futex) < 0) {
124	rc = __SYSCALL3(SYS_FUTEX_SLEEP, (sysarg_t) &futex->count,	124	rc = __SYSCALL3(SYS_FUTEX_SLEEP, (sysarg_t) &futex->count,
125	(sysarg_t) usec, (sysarg_t) flags);	125	(sysarg_t) usec, (sysarg_t) flags);
126		126
127	switch (rc) {	127	switch (rc) {
128	case ESYNCH_OK_ATOMIC:	128	case ESYNCH_OK_ATOMIC:
129	/*	129	/*
130	* Because of a race condition between timeout and	130	* Because of a race condition between timeout and
131	* futex_up() and between conditional	131	* futex_up() and between conditional
132	* futex_down_timeout() and futex_up(), we have to give	132	* futex_down_timeout() and futex_up(), we have to give
133	* up and try again in this special case.	133	* up and try again in this special case.
134	*/	134	*/
135	atomic_inc(futex);	135	atomic_inc(futex);
136	break;	136	break;
137		137
138	case ESYNCH_TIMEOUT:	138	case ESYNCH_TIMEOUT:
139	atomic_inc(futex);	139	atomic_inc(futex);
140	return ESYNCH_TIMEOUT;	140	return ESYNCH_TIMEOUT;
141	break;	141	break;
142		142
143	case ESYNCH_WOULD_BLOCK:	143	case ESYNCH_WOULD_BLOCK:
144	/*	144	/*
145	* The conditional down operation should be implemented	145	* The conditional down operation should be implemented
146	* this way. The userspace-only variant tends to	146	* this way. The userspace-only variant tends to
147	* accumulate missed wakeups in the kernel futex wait	147	* accumulate missed wakeups in the kernel futex wait
148	* queue.	148	* queue.
149	*/	149	*/
150	atomic_inc(futex);	150	atomic_inc(futex);
151	return ESYNCH_WOULD_BLOCK;	151	return ESYNCH_WOULD_BLOCK;
152	break;	152	break;
153		153
154	case ESYNCH_OK_BLOCKED:	154	case ESYNCH_OK_BLOCKED:
155	/*	155	/*
156	* Enter the critical section.	156	* Enter the critical section.
157	* The futex counter has already been incremented for	157	* The futex counter has already been incremented for
158	* us.	158	* us.
159	*/	159	*/
160	return ESYNCH_OK_BLOCKED;	160	return ESYNCH_OK_BLOCKED;
161	break;	161	break;
162	default:	162	default:
163	return rc;	163	return rc;
164	}	164	}
165	}	165	}
166		166
167	/*	167	/*
168	* Enter the critical section.	168	* Enter the critical section.
169	*/	169	*/
170	return ESYNCH_OK_ATOMIC;	170	return ESYNCH_OK_ATOMIC;
171	}	171	}
172		172
173	/** Up the futex.	173	/** Up the futex.
174	*	174	*
175	* @param futex Futex.	175	* @param futex Futex.
176	*	176	*
177	* @return ENOENT if there is no such virtual address. Otherwise	177	* @return ENOENT if there is no such virtual address. Otherwise
178	* zero.	178	* zero.
179	*/	179	*/
180	int futex_up(futex_t *futex)	180	int futex_up(futex_t *futex)
181	{	181	{
182	long val;	182	long val;
183		183
184	val = atomic_postinc(futex);	184	val = atomic_postinc(futex);
185	if (val < 0)	185	if (val < 0)
186	return __SYSCALL1(SYS_FUTEX_WAKEUP, (sysarg_t) &futex->count);	186	return __SYSCALL1(SYS_FUTEX_WAKEUP, (sysarg_t) &futex->count);
187		187
188	return 0;	188	return 0;
189	}	189	}
190		190
191	/** @}	191	/** @}
192	*/	192	*/
193		193

Subversion Repositories HelenOS

(root)/branches/arm/uspace/lib/libc/generic/futex.c – Rev 2682 → 3478