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

Rev	Author	Line No.	Line
1111	jermar	1	/*
		2	* Copyright (C) 2006 Jakub Jermar
		3	* All rights reserved.
		4	*
		5	* Redistribution and use in source and binary forms, with or without
		6	* modification, are permitted provided that the following conditions
		7	* are met:
		8	*
		9	* - Redistributions of source code must retain the above copyright
		10	* notice, this list of conditions and the following disclaimer.
		11	* - Redistributions in binary form must reproduce the above copyright
		12	* notice, this list of conditions and the following disclaimer in the
		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
		15	* derived from this software without specific prior written permission.
		16	*
		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
		19	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
		20	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
		21	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
		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
		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
		26	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
		27	*/
		28
		29	#include <futex.h>
		30	#include <atomic.h>
		31	#include <libc.h>
		32	#include <stdio.h>
1116	jermar	33	#include <types.h>
		34	#include <kernel/synch/synch.h>
1111	jermar	35
1116	jermar	36	/*
		37	* Note about race conditions.
		38	* Because of non-atomic nature of operations performed sequentially on the futex
		39	* counter and the futex wait queue, there is a race condition:
		40	*
1152	jermar	41	* (wq->missed_wakeups == 1) && (futex->count = 1)
1116	jermar	42	*
		43	* Scenario 1 (wait queue timeout vs. futex_up()):
		44	* 1. assume wq->missed_wakeups == 0 && futex->count == -1
		45	* (ie. thread A sleeping, thread B in the critical section)
		46	* 2. A receives timeout and gets removed from the wait queue
		47	* 3. B wants to leave the critical section and calls futex_up()
		48	* 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
		50	* 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
		52	*
		53	* Scenario 2 (conditional down operation vs. futex_up)
		54	* 1. assume wq->missed_wakeups == 0 && futex->count == 0
		55	* (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
		57	* B is now obliged to call SYS_FUTEX_SLEEP syscall
		58	* 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
		60	* 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
		62	* 6. B fixes futex->count (i.e. the number of waiting threads) by changing it from 0 to 1
		63	*
		64	* 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.
		66	*
		67	* 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.
		69	*
		70	*/
		71
		72	/** Initialize futex counter.
		73	*
		74	* @param futex Futex.
		75	* @param val Initialization value.
		76	*/
1111	jermar	77	void futex_initialize(atomic_t *futex, int val)
		78	{
		79	atomic_set(futex, val);
		80	}
		81
		82	int futex_down(atomic_t *futex)
		83	{
1116	jermar	84	return futex_down_timeout(futex, SYNCH_NO_TIMEOUT, SYNCH_BLOCKING);
		85	}
		86
		87	int futex_trydown(atomic_t *futex)
		88	{
		89	return futex_down_timeout(futex, SYNCH_NO_TIMEOUT, SYNCH_NON_BLOCKING);
		90	}
		91
		92	/** Try to down the futex.
		93	*
		94	* @param futex Futex.
		95	* @param usec Microseconds to wait. Zero value means sleep without timeout.
		96	* @param trydown If usec is zero and trydown is non-zero, only conditional
		97	*
		98	* @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
		100	* not acquired because of a timeout or ESYNCH_WOULD_BLOCK if the
		101	* operation could not be carried out atomically (if requested so).
		102	*/
		103	int futex_down_timeout(atomic_t *futex, uint32_t usec, int trydown)
		104	{
		105	int rc;
1111	jermar	106
1116	jermar	107	while (atomic_predec(futex) < 0) {
		108	rc = __SYSCALL3(SYS_FUTEX_SLEEP, (sysarg_t) &futex->count, (sysarg_t) usec, (sysarg_t) trydown);
1111	jermar	109
1116	jermar	110	switch (rc) {
		111	case ESYNCH_OK_ATOMIC:
		112	/*
		113	* Because of a race condition between timeout and futex_up()
		114	* and between conditional futex_down_timeout() and futex_up(),
		115	* we have to give up and try again in this special case.
		116	*/
		117	atomic_inc(futex);
		118	break;
		119
		120	case ESYNCH_TIMEOUT:
		121	atomic_inc(futex);
		122	return ESYNCH_TIMEOUT;
		123	break;
		124
		125	case ESYNCH_WOULD_BLOCK:
		126	/*
		127	* The conditional down operation should be implemented this way.
		128	* The userspace-only variant tends to accumulate missed wakeups
		129	* in the kernel futex wait queue.
		130	*/
		131	atomic_inc(futex);
		132	return ESYNCH_WOULD_BLOCK;
		133	break;
		134
		135	case ESYNCH_OK_BLOCKED:
		136	/*
		137	* Enter the critical section.
		138	* The futex counter has already been incremented for us.
		139	*/
		140	return ESYNCH_OK_BLOCKED;
		141	break;
		142	default:
		143	return rc;
		144	}
		145	}
		146
		147	/*
		148	* Enter the critical section.
		149	*/
		150	return ESYNCH_OK_ATOMIC;
1111	jermar	151	}
		152
1116	jermar	153	/** Up the futex.
		154	*
		155	* @param futex Futex.
		156	*
1152	jermar	157	* @return ENOENT if there is no such virtual address. Otherwise zero.
1116	jermar	158	*/
1111	jermar	159	int futex_up(atomic_t *futex)
		160	{
1114	jermar	161	long val;
		162
		163	val = atomic_postinc(futex);
		164	if (val < 0)
1111	jermar	165	return __SYSCALL1(SYS_FUTEX_WAKEUP, (sysarg_t) &futex->count);
		166
		167	return 0;
		168	}

Subversion Repositories HelenOS-historic

(root)//uspace/trunk/libc/generic/futex.c – Rev 1152