WebSVN – HelenOS – Diff – /trunk/uspace/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

(root)/trunk/uspace/libc/generic/futex.c – Rev 1866 → 2071

Rev 1866		Rev 2071
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	*/	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 <types.h>	39	#include <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 futex	44	* Because of non-atomic nature of operations performed sequentially on the futex
45	* counter and the futex wait queue, there is a race condition:	45	* 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 from 0 to 1	57	* 7. A fixes futex->count (i.e. the number of waiting threads) by changing it from 0 to 1
58	*	58	*
59	* Scenario 2 (conditional down operation vs. futex_up)	59	* Scenario 2 (conditional down operation vs. futex_up)
60	* 1. assume wq->missed_wakeups == 0 && futex->count == 0	60	* 1. assume wq->missed_wakeups == 0 && futex->count == 0
61	* (i.e. thread A is in the critical section)	61	* (i.e. thread A is in the critical section)
62	* 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
63	* B is now obliged to call SYS_FUTEX_SLEEP syscall	63	* B is now obliged to call SYS_FUTEX_SLEEP syscall
64	* 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()
65	* 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
66	* 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
67	* 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
68	* 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
69	*	69	*
70	* 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.
71	* 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.
72	*	72	*
73	* 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
74	* 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.
75	*	75	*
76	*/	76	*/
77		77
78	/** Initialize futex counter.	78	/** Initialize futex counter.
79	*	79	*
80	* @param futex Futex.	80	* @param futex Futex.
81	* @param val Initialization value.	81	* @param val Initialization value.
82	*/	82	*/
83	void futex_initialize(atomic_t *futex, int val)	83	void futex_initialize(atomic_t *futex, int val)
84	{	84	{
85	atomic_set(futex, val);	85	atomic_set(futex, val);
86	}	86	}
87		87
88	int futex_down(atomic_t *futex)	88	int futex_down(atomic_t *futex)
89	{	89	{
90	return futex_down_timeout(futex, SYNCH_NO_TIMEOUT, SYNCH_FLAGS_NONE);	90	return futex_down_timeout(futex, SYNCH_NO_TIMEOUT, SYNCH_FLAGS_NONE);
91	}	91	}
92		92
93	int futex_trydown(atomic_t *futex)	93	int futex_trydown(atomic_t *futex)
94	{	94	{
95	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);
96	}	96	}
97		97
98	/** Try to down the futex.	98	/** Try to down the futex.
99	*	99	*
100	* @param futex Futex.	100	* @param futex Futex.
101	* @param usec Microseconds to wait. Zero value means sleep without timeout.	101	* @param usec Microseconds to wait. Zero value means sleep without timeout.
102	* @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().
103	*	103	*
104	* @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
105	* 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
106	* 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
107	* operation could not be carried out atomically (if requested so).	107	* operation could not be carried out atomically (if requested so).
108	*/	108	*/
109	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)
110	{	110	{
111	int rc;	111	int rc;
112		112
113	while (atomic_predec(futex) < 0) {	113	while (atomic_predec(futex) < 0) {
114	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);
115		115
116	switch (rc) {	116	switch (rc) {
117	case ESYNCH_OK_ATOMIC:	117	case ESYNCH_OK_ATOMIC:
118	/*	118	/*
119	* Because of a race condition between timeout and futex_up()	119	* Because of a race condition between timeout and futex_up()
120	* and between conditional futex_down_timeout() and futex_up(),	120	* and between conditional futex_down_timeout() and futex_up(),
121	* 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.
122	*/	122	*/
123	atomic_inc(futex);	123	atomic_inc(futex);
124	break;	124	break;
125		125
126	case ESYNCH_TIMEOUT:	126	case ESYNCH_TIMEOUT:
127	atomic_inc(futex);	127	atomic_inc(futex);
128	return ESYNCH_TIMEOUT;	128	return ESYNCH_TIMEOUT;
129	break;	129	break;
130		130
131	case ESYNCH_WOULD_BLOCK:	131	case ESYNCH_WOULD_BLOCK:
132	/*	132	/*
133	* The conditional down operation should be implemented this way.	133	* The conditional down operation should be implemented this way.
134	* The userspace-only variant tends to accumulate missed wakeups	134	* The userspace-only variant tends to accumulate missed wakeups
135	* in the kernel futex wait queue.	135	* in the kernel futex wait queue.
136	*/	136	*/
137	atomic_inc(futex);	137	atomic_inc(futex);
138	return ESYNCH_WOULD_BLOCK;	138	return ESYNCH_WOULD_BLOCK;
139	break;	139	break;
140		140
141	case ESYNCH_OK_BLOCKED:	141	case ESYNCH_OK_BLOCKED:
142	/*	142	/*
143	* Enter the critical section.	143	* Enter the critical section.
144	* The futex counter has already been incremented for us.	144	* The futex counter has already been incremented for us.
145	*/	145	*/
146	return ESYNCH_OK_BLOCKED;	146	return ESYNCH_OK_BLOCKED;
147	break;	147	break;
148	default:	148	default:
149	return rc;	149	return rc;
150	}	150	}
151	}	151	}
152		152
153	/*	153	/*
154	* Enter the critical section.	154	* Enter the critical section.
155	*/	155	*/
156	return ESYNCH_OK_ATOMIC;	156	return ESYNCH_OK_ATOMIC;
157	}	157	}
158		158
159	/** Up the futex.	159	/** Up the futex.
160	*	160	*
161	* @param futex Futex.	161	* @param futex Futex.
162	*	162	*
163	* @return ENOENT if there is no such virtual address. Otherwise zero.	163	* @return ENOENT if there is no such virtual address. Otherwise zero.
164	*/	164	*/
165	int futex_up(atomic_t *futex)	165	int futex_up(atomic_t *futex)
166	{	166	{
167	long val;	167	long val;
168		168
169	val = atomic_postinc(futex);	169	val = atomic_postinc(futex);
170	if (val < 0)	170	if (val < 0)
171	return __SYSCALL1(SYS_FUTEX_WAKEUP, (sysarg_t) &futex->count);	171	return __SYSCALL1(SYS_FUTEX_WAKEUP, (sysarg_t) &futex->count);
172		172
173	return 0;	173	return 0;
174	}	174	}
175		175
176	/** @}	176	/** @}
177	*/	177	*/
178		178