WebSVN – HelenOS-historic – Diff – /kernel/trunk/generic/src/synch/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 sync
 * @{
 */
 
/**
 * @file
 * @brief   Kernel backend for futexes.
 */
 
#include <synch/futex.h>
#include <synch/rwlock.h>
#include <synch/spinlock.h>
#include <synch/synch.h>
#include <mm/frame.h>
#include <mm/page.h>
#include <mm/slab.h>
#include <proc/thread.h>
#include <proc/task.h>
#include <genarch/mm/page_pt.h>
#include <genarch/mm/page_ht.h>
#include <adt/hash_table.h>
#include <adt/list.h>
#include <arch.h>
#include <align.h>
#include <panic.h>
#include <errno.h>
#include <print.h>
 
#define FUTEX_HT_SIZE   1024    /* keep it a power of 2 */
 
static void futex_initialize(futex_t *futex);
 
static futex_t *futex_find(__address paddr);
static index_t futex_ht_hash(__native *key);
static bool futex_ht_compare(__native *key, count_t keys, link_t *item);
static void futex_ht_remove_callback(link_t *item);
 
/**
 * Read-write lock protecting global futex hash table.
 * It is also used to serialize access to all futex_t structures.
 * Must be acquired before the task futex B+tree lock.
 */
static rwlock_t futex_ht_lock;
 
/** Futex hash table. */
static hash_table_t futex_ht;
 
/** Futex hash table operations. */
static hash_table_operations_t futex_ht_ops = {
    .hash = futex_ht_hash,
    .compare = futex_ht_compare,
    .remove_callback = futex_ht_remove_callback
};
 
/** Initialize futex subsystem. */
void futex_init(void)
{
    rwlock_initialize(&futex_ht_lock);
    hash_table_create(&futex_ht, FUTEX_HT_SIZE, 1, &futex_ht_ops);
}
 
/** Initialize kernel futex structure.
 *
 * @param futex Kernel futex structure.
 */
void futex_initialize(futex_t *futex)
{
    waitq_initialize(&futex->wq);
    link_initialize(&futex->ht_link);
    futex->paddr = 0;
    futex->refcount = 1;
}
 
/** Sleep in futex wait queue.
 *
 * @param uaddr Userspace address of the futex counter.
 * @param usec If non-zero, number of microseconds this thread is willing to sleep.
 * @param flags Select mode of operation.
 *
 * @return One of ESYNCH_TIMEOUT, ESYNCH_OK_ATOMIC and ESYNCH_OK_BLOCKED. See synch.h.
 *     If there is no physical mapping for uaddr ENOENT is returned.
 */
__native sys_futex_sleep_timeout(__address uaddr, __u32 usec, int flags)
{
    futex_t *futex;
    __address paddr;
    pte_t *t;
    ipl_t ipl;
   
    ipl = interrupts_disable();
 
    /*
     * Find physical address of futex counter.
     */
    page_table_lock(AS, true);
    t = page_mapping_find(AS, ALIGN_DOWN(uaddr, PAGE_SIZE));
    if (!t || !PTE_VALID(t) || !PTE_PRESENT(t)) {
        page_table_unlock(AS, true);
        interrupts_restore(ipl);
        return (__native) ENOENT;
    }
    paddr = PTE_GET_FRAME(t) + (uaddr - ALIGN_DOWN(uaddr, PAGE_SIZE));
    page_table_unlock(AS, true);
   
    interrupts_restore(ipl);   
 
    futex = futex_find(paddr);
   
    return (__native) waitq_sleep_timeout(&futex->wq, usec, flags | SYNCH_FLAGS_INTERRUPTIBLE);
}
 
/** Wakeup one thread waiting in futex wait queue.
 *
 * @param uaddr Userspace address of the futex counter.
 *
 * @return ENOENT if there is no physical mapping for uaddr.
 */
__native sys_futex_wakeup(__address uaddr)
{
    futex_t *futex;
    __address paddr;
    pte_t *t;
    ipl_t ipl;
   
    ipl = interrupts_disable();
   
    /*
     * Find physical address of futex counter.
     */
    page_table_lock(AS, true);
    t = page_mapping_find(AS, ALIGN_DOWN(uaddr, PAGE_SIZE));
    if (!t || !PTE_VALID(t) || !PTE_PRESENT(t)) {
        page_table_unlock(AS, true);
        interrupts_restore(ipl);
        return (__native) ENOENT;
    }
    paddr = PTE_GET_FRAME(t) + (uaddr - ALIGN_DOWN(uaddr, PAGE_SIZE));
    page_table_unlock(AS, true);
   
    interrupts_restore(ipl);
 
    futex = futex_find(paddr);
       
    waitq_wakeup(&futex->wq, WAKEUP_FIRST);
   
    return 0;
}
 
/** Find kernel address of the futex structure corresponding to paddr.
 *
 * If the structure does not exist already, a new one is created.
 *
 * @param paddr Physical address of the userspace futex counter.
 *
 * @return Address of the kernel futex structure.
 */
futex_t *futex_find(__address paddr)
{
    link_t *item;
    futex_t *futex;
    btree_node_t *leaf;
   
    /*
     * Find the respective futex structure
     * or allocate new one if it does not exist already.
     */
    rwlock_read_lock(&futex_ht_lock);
    item = hash_table_find(&futex_ht, &paddr);
    if (item) {
        futex = hash_table_get_instance(item, futex_t, ht_link);
 
        /*
         * See if the current task knows this futex.
         */
        mutex_lock(&TASK->futexes_lock);
        if (!btree_search(&TASK->futexes, paddr, &leaf)) {
            /*
             * The futex is new to the current task.
             * However, we only have read access.
             * Gain write access and try again.
             */
            mutex_unlock(&TASK->futexes_lock);
            goto gain_write_access;
        }
        mutex_unlock(&TASK->futexes_lock);
 
        rwlock_read_unlock(&futex_ht_lock);
    } else {
gain_write_access:
        /*
         * Upgrade to writer is not currently supported,
         * therefore, it is necessary to release the read lock
         * and reacquire it as a writer.
         */
        rwlock_read_unlock(&futex_ht_lock);
 
        rwlock_write_lock(&futex_ht_lock);
        /*
         * Avoid possible race condition by searching
         * the hash table once again with write access.
         */
        item = hash_table_find(&futex_ht, &paddr);
        if (item) {
            futex = hash_table_get_instance(item, futex_t, ht_link);
           
            /*
             * See if this futex is known to the current task.
             */
            mutex_lock(&TASK->futexes_lock);
            if (!btree_search(&TASK->futexes, paddr, &leaf)) {
                /*
                 * The futex is new to the current task.
                 * Upgrade its reference count and put it to the
                 * current task's B+tree of known futexes.
                 */
                futex->refcount++;
                btree_insert(&TASK->futexes, paddr, futex, leaf);
            }
            mutex_unlock(&TASK->futexes_lock);
   
            rwlock_write_unlock(&futex_ht_lock);
        } else {
            futex = (futex_t *) malloc(sizeof(futex_t), 0);
            futex_initialize(futex);
            futex->paddr = paddr;
            hash_table_insert(&futex_ht, &paddr, &futex->ht_link);
           
            /*
             * This is the first task referencing the futex.
             * It can be directly inserted into its
             * B+tree of known futexes.
             */
            mutex_lock(&TASK->futexes_lock);
            btree_insert(&TASK->futexes, paddr, futex, NULL);
            mutex_unlock(&TASK->futexes_lock);
           
            rwlock_write_unlock(&futex_ht_lock);
        }
    }
   
    return futex;
}
 
/** Compute hash index into futex hash table.
 *
 * @param key Address where the key (i.e. physical address of futex counter) is stored.
 *
 * @return Index into futex hash table.
 */
index_t futex_ht_hash(__native *key)
{
    return *key & (FUTEX_HT_SIZE-1);
}
 
/** Compare futex hash table item with a key.
 *
 * @param key Address where the key (i.e. physical address of futex counter) is stored.
 *
 * @return True if the item matches the key. False otherwise.
 */
bool futex_ht_compare(__native *key, count_t keys, link_t *item)
{
    futex_t *futex;
 
    ASSERT(keys == 1);
 
    futex = hash_table_get_instance(item, futex_t, ht_link);
    return *key == futex->paddr;
}
 
/** Callback for removal items from futex hash table.
 *
 * @param item Item removed from the hash table.
 */
void futex_ht_remove_callback(link_t *item)
{
    futex_t *futex;
 
    futex = hash_table_get_instance(item, futex_t, ht_link);
    free(futex);
}
 
/** Remove references from futexes known to the current task. */
void futex_cleanup(void)
{
    link_t *cur;
   
    rwlock_write_lock(&futex_ht_lock);
    mutex_lock(&TASK->futexes_lock);
 
    for (cur = TASK->futexes.leaf_head.next; cur != &TASK->futexes.leaf_head; cur = cur->next) {
        btree_node_t *node;
        int i;
       
        node = list_get_instance(cur, btree_node_t, leaf_link);
        for (i = 0; i < node->keys; i++) {
            futex_t *ftx;
            __address paddr = node->key[i];
           
            ftx = (futex_t *) node->value[i];
            if (--ftx->refcount == 0)
                hash_table_remove(&futex_ht, &paddr, 1);
        }
    }
   
    mutex_unlock(&TASK->futexes_lock);
    rwlock_write_unlock(&futex_ht_lock);
}
 
 /** @}
 */
 
 

Subversion Repositories HelenOS-historic

(root)/kernel/trunk/generic/src/synch/futex.c – Rev 1586 → 1702

Rev 1586		Rev 1702
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 sync
-		30	* @{
-		31	*/
-		32
29	/**	33	/**
30	* @file futex.c	34	* @file
31	* @brief Kernel backend for futexes.	35	* @brief Kernel backend for futexes.
32	*/	36	*/
33		37
34	#include <synch/futex.h>	38	#include <synch/futex.h>
35	#include <synch/rwlock.h>	39	#include <synch/rwlock.h>
36	#include <synch/spinlock.h>	40	#include <synch/spinlock.h>
37	#include <synch/synch.h>	41	#include <synch/synch.h>
38	#include <mm/frame.h>	42	#include <mm/frame.h>
39	#include <mm/page.h>	43	#include <mm/page.h>
40	#include <mm/slab.h>	44	#include <mm/slab.h>
41	#include <proc/thread.h>	45	#include <proc/thread.h>
42	#include <proc/task.h>	46	#include <proc/task.h>
43	#include <genarch/mm/page_pt.h>	47	#include <genarch/mm/page_pt.h>
44	#include <genarch/mm/page_ht.h>	48	#include <genarch/mm/page_ht.h>
45	#include <adt/hash_table.h>	49	#include <adt/hash_table.h>
46	#include <adt/list.h>	50	#include <adt/list.h>
47	#include <arch.h>	51	#include <arch.h>
48	#include <align.h>	52	#include <align.h>
49	#include <panic.h>	53	#include <panic.h>
50	#include <errno.h>	54	#include <errno.h>
51	#include <print.h>	55	#include <print.h>
52		56
53	#define FUTEX_HT_SIZE 1024 /* keep it a power of 2 */	57	#define FUTEX_HT_SIZE 1024 /* keep it a power of 2 */
54		58
55	static void futex_initialize(futex_t *futex);	59	static void futex_initialize(futex_t *futex);
56		60
57	static futex_t *futex_find(__address paddr);	61	static futex_t *futex_find(__address paddr);
58	static index_t futex_ht_hash(__native *key);	62	static index_t futex_ht_hash(__native *key);
59	static bool futex_ht_compare(__native key, count_t keys, link_t item);	63	static bool futex_ht_compare(__native key, count_t keys, link_t item);
60	static void futex_ht_remove_callback(link_t *item);	64	static void futex_ht_remove_callback(link_t *item);
61		65
62	/**	66	/**
63	* Read-write lock protecting global futex hash table.	67	* Read-write lock protecting global futex hash table.
64	* It is also used to serialize access to all futex_t structures.	68	* It is also used to serialize access to all futex_t structures.
65	* Must be acquired before the task futex B+tree lock.	69	* Must be acquired before the task futex B+tree lock.
66	*/	70	*/
67	static rwlock_t futex_ht_lock;	71	static rwlock_t futex_ht_lock;
68		72
69	/** Futex hash table. */	73	/** Futex hash table. */
70	static hash_table_t futex_ht;	74	static hash_table_t futex_ht;
71		75
72	/** Futex hash table operations. */	76	/** Futex hash table operations. */
73	static hash_table_operations_t futex_ht_ops = {	77	static hash_table_operations_t futex_ht_ops = {
74	.hash = futex_ht_hash,	78	.hash = futex_ht_hash,
75	.compare = futex_ht_compare,	79	.compare = futex_ht_compare,
76	.remove_callback = futex_ht_remove_callback	80	.remove_callback = futex_ht_remove_callback
77	};	81	};
78		82
79	/** Initialize futex subsystem. */	83	/** Initialize futex subsystem. */
80	void futex_init(void)	84	void futex_init(void)
81	{	85	{
82	rwlock_initialize(&futex_ht_lock);	86	rwlock_initialize(&futex_ht_lock);
83	hash_table_create(&futex_ht, FUTEX_HT_SIZE, 1, &futex_ht_ops);	87	hash_table_create(&futex_ht, FUTEX_HT_SIZE, 1, &futex_ht_ops);
84	}	88	}
85		89
86	/** Initialize kernel futex structure.	90	/** Initialize kernel futex structure.
87	*	91	*
88	* @param futex Kernel futex structure.	92	* @param futex Kernel futex structure.
89	*/	93	*/
90	void futex_initialize(futex_t *futex)	94	void futex_initialize(futex_t *futex)
91	{	95	{
92	waitq_initialize(&futex->wq);	96	waitq_initialize(&futex->wq);
93	link_initialize(&futex->ht_link);	97	link_initialize(&futex->ht_link);
94	futex->paddr = 0;	98	futex->paddr = 0;
95	futex->refcount = 1;	99	futex->refcount = 1;
96	}	100	}
97		101
98	/** Sleep in futex wait queue.	102	/** Sleep in futex wait queue.
99	*	103	*
100	* @param uaddr Userspace address of the futex counter.	104	* @param uaddr Userspace address of the futex counter.
101	* @param usec If non-zero, number of microseconds this thread is willing to sleep.	105	* @param usec If non-zero, number of microseconds this thread is willing to sleep.
102	* @param flags Select mode of operation.	106	* @param flags Select mode of operation.
103	*	107	*
104	* @return One of ESYNCH_TIMEOUT, ESYNCH_OK_ATOMIC and ESYNCH_OK_BLOCKED. See synch.h.	108	* @return One of ESYNCH_TIMEOUT, ESYNCH_OK_ATOMIC and ESYNCH_OK_BLOCKED. See synch.h.
105	* If there is no physical mapping for uaddr ENOENT is returned.	109	* If there is no physical mapping for uaddr ENOENT is returned.
106	*/	110	*/
107	__native sys_futex_sleep_timeout(__address uaddr, __u32 usec, int flags)	111	__native sys_futex_sleep_timeout(__address uaddr, __u32 usec, int flags)
108	{	112	{
109	futex_t *futex;	113	futex_t *futex;
110	__address paddr;	114	__address paddr;
111	pte_t *t;	115	pte_t *t;
112	ipl_t ipl;	116	ipl_t ipl;
113		117
114	ipl = interrupts_disable();	118	ipl = interrupts_disable();
115		119
116	/*	120	/*
117	* Find physical address of futex counter.	121	* Find physical address of futex counter.
118	*/	122	*/
119	page_table_lock(AS, true);	123	page_table_lock(AS, true);
120	t = page_mapping_find(AS, ALIGN_DOWN(uaddr, PAGE_SIZE));	124	t = page_mapping_find(AS, ALIGN_DOWN(uaddr, PAGE_SIZE));
121	if (!t \|\| !PTE_VALID(t) \|\| !PTE_PRESENT(t)) {	125	if (!t \|\| !PTE_VALID(t) \|\| !PTE_PRESENT(t)) {
122	page_table_unlock(AS, true);	126	page_table_unlock(AS, true);
123	interrupts_restore(ipl);	127	interrupts_restore(ipl);
124	return (__native) ENOENT;	128	return (__native) ENOENT;
125	}	129	}
126	paddr = PTE_GET_FRAME(t) + (uaddr - ALIGN_DOWN(uaddr, PAGE_SIZE));	130	paddr = PTE_GET_FRAME(t) + (uaddr - ALIGN_DOWN(uaddr, PAGE_SIZE));
127	page_table_unlock(AS, true);	131	page_table_unlock(AS, true);
128		132
129	interrupts_restore(ipl);	133	interrupts_restore(ipl);
130		134
131	futex = futex_find(paddr);	135	futex = futex_find(paddr);
132		136
133	return (__native) waitq_sleep_timeout(&futex->wq, usec, flags \| SYNCH_FLAGS_INTERRUPTIBLE);	137	return (__native) waitq_sleep_timeout(&futex->wq, usec, flags \| SYNCH_FLAGS_INTERRUPTIBLE);
134	}	138	}
135		139
136	/** Wakeup one thread waiting in futex wait queue.	140	/** Wakeup one thread waiting in futex wait queue.
137	*	141	*
138	* @param uaddr Userspace address of the futex counter.	142	* @param uaddr Userspace address of the futex counter.
139	*	143	*
140	* @return ENOENT if there is no physical mapping for uaddr.	144	* @return ENOENT if there is no physical mapping for uaddr.
141	*/	145	*/
142	__native sys_futex_wakeup(__address uaddr)	146	__native sys_futex_wakeup(__address uaddr)
143	{	147	{
144	futex_t *futex;	148	futex_t *futex;
145	__address paddr;	149	__address paddr;
146	pte_t *t;	150	pte_t *t;
147	ipl_t ipl;	151	ipl_t ipl;
148		152
149	ipl = interrupts_disable();	153	ipl = interrupts_disable();
150		154
151	/*	155	/*
152	* Find physical address of futex counter.	156	* Find physical address of futex counter.
153	*/	157	*/
154	page_table_lock(AS, true);	158	page_table_lock(AS, true);
155	t = page_mapping_find(AS, ALIGN_DOWN(uaddr, PAGE_SIZE));	159	t = page_mapping_find(AS, ALIGN_DOWN(uaddr, PAGE_SIZE));
156	if (!t \|\| !PTE_VALID(t) \|\| !PTE_PRESENT(t)) {	160	if (!t \|\| !PTE_VALID(t) \|\| !PTE_PRESENT(t)) {
157	page_table_unlock(AS, true);	161	page_table_unlock(AS, true);
158	interrupts_restore(ipl);	162	interrupts_restore(ipl);
159	return (__native) ENOENT;	163	return (__native) ENOENT;
160	}	164	}
161	paddr = PTE_GET_FRAME(t) + (uaddr - ALIGN_DOWN(uaddr, PAGE_SIZE));	165	paddr = PTE_GET_FRAME(t) + (uaddr - ALIGN_DOWN(uaddr, PAGE_SIZE));
162	page_table_unlock(AS, true);	166	page_table_unlock(AS, true);
163		167
164	interrupts_restore(ipl);	168	interrupts_restore(ipl);
165		169
166	futex = futex_find(paddr);	170	futex = futex_find(paddr);
167		171
168	waitq_wakeup(&futex->wq, WAKEUP_FIRST);	172	waitq_wakeup(&futex->wq, WAKEUP_FIRST);
169		173
170	return 0;	174	return 0;
171	}	175	}
172		176
173	/** Find kernel address of the futex structure corresponding to paddr.	177	/** Find kernel address of the futex structure corresponding to paddr.
174	*	178	*
175	* If the structure does not exist already, a new one is created.	179	* If the structure does not exist already, a new one is created.
176	*	180	*
177	* @param paddr Physical address of the userspace futex counter.	181	* @param paddr Physical address of the userspace futex counter.
178	*	182	*
179	* @return Address of the kernel futex structure.	183	* @return Address of the kernel futex structure.
180	*/	184	*/
181	futex_t *futex_find(__address paddr)	185	futex_t *futex_find(__address paddr)
182	{	186	{
183	link_t *item;	187	link_t *item;
184	futex_t *futex;	188	futex_t *futex;
185	btree_node_t *leaf;	189	btree_node_t *leaf;
186		190
187	/*	191	/*
188	* Find the respective futex structure	192	* Find the respective futex structure
189	* or allocate new one if it does not exist already.	193	* or allocate new one if it does not exist already.
190	*/	194	*/
191	rwlock_read_lock(&futex_ht_lock);	195	rwlock_read_lock(&futex_ht_lock);
192	item = hash_table_find(&futex_ht, &paddr);	196	item = hash_table_find(&futex_ht, &paddr);
193	if (item) {	197	if (item) {
194	futex = hash_table_get_instance(item, futex_t, ht_link);	198	futex = hash_table_get_instance(item, futex_t, ht_link);
195		199
196	/*	200	/*
197	* See if the current task knows this futex.	201	* See if the current task knows this futex.
198	*/	202	*/
199	mutex_lock(&TASK->futexes_lock);	203	mutex_lock(&TASK->futexes_lock);
200	if (!btree_search(&TASK->futexes, paddr, &leaf)) {	204	if (!btree_search(&TASK->futexes, paddr, &leaf)) {
201	/*	205	/*
202	* The futex is new to the current task.	206	* The futex is new to the current task.
203	* However, we only have read access.	207	* However, we only have read access.
204	* Gain write access and try again.	208	* Gain write access and try again.
205	*/	209	*/
206	mutex_unlock(&TASK->futexes_lock);	210	mutex_unlock(&TASK->futexes_lock);
207	goto gain_write_access;	211	goto gain_write_access;
208	}	212	}
209	mutex_unlock(&TASK->futexes_lock);	213	mutex_unlock(&TASK->futexes_lock);
210		214
211	rwlock_read_unlock(&futex_ht_lock);	215	rwlock_read_unlock(&futex_ht_lock);
212	} else {	216	} else {
213	gain_write_access:	217	gain_write_access:
214	/*	218	/*
215	* Upgrade to writer is not currently supported,	219	* Upgrade to writer is not currently supported,
216	* therefore, it is necessary to release the read lock	220	* therefore, it is necessary to release the read lock
217	* and reacquire it as a writer.	221	* and reacquire it as a writer.
218	*/	222	*/
219	rwlock_read_unlock(&futex_ht_lock);	223	rwlock_read_unlock(&futex_ht_lock);
220		224
221	rwlock_write_lock(&futex_ht_lock);	225	rwlock_write_lock(&futex_ht_lock);
222	/*	226	/*
223	* Avoid possible race condition by searching	227	* Avoid possible race condition by searching
224	* the hash table once again with write access.	228	* the hash table once again with write access.
225	*/	229	*/
226	item = hash_table_find(&futex_ht, &paddr);	230	item = hash_table_find(&futex_ht, &paddr);
227	if (item) {	231	if (item) {
228	futex = hash_table_get_instance(item, futex_t, ht_link);	232	futex = hash_table_get_instance(item, futex_t, ht_link);
229		233
230	/*	234	/*
231	* See if this futex is known to the current task.	235	* See if this futex is known to the current task.
232	*/	236	*/
233	mutex_lock(&TASK->futexes_lock);	237	mutex_lock(&TASK->futexes_lock);
234	if (!btree_search(&TASK->futexes, paddr, &leaf)) {	238	if (!btree_search(&TASK->futexes, paddr, &leaf)) {
235	/*	239	/*
236	* The futex is new to the current task.	240	* The futex is new to the current task.
237	* Upgrade its reference count and put it to the	241	* Upgrade its reference count and put it to the
238	* current task's B+tree of known futexes.	242	* current task's B+tree of known futexes.
239	*/	243	*/
240	futex->refcount++;	244	futex->refcount++;
241	btree_insert(&TASK->futexes, paddr, futex, leaf);	245	btree_insert(&TASK->futexes, paddr, futex, leaf);
242	}	246	}
243	mutex_unlock(&TASK->futexes_lock);	247	mutex_unlock(&TASK->futexes_lock);
244		248
245	rwlock_write_unlock(&futex_ht_lock);	249	rwlock_write_unlock(&futex_ht_lock);
246	} else {	250	} else {
247	futex = (futex_t *) malloc(sizeof(futex_t), 0);	251	futex = (futex_t *) malloc(sizeof(futex_t), 0);
248	futex_initialize(futex);	252	futex_initialize(futex);
249	futex->paddr = paddr;	253	futex->paddr = paddr;
250	hash_table_insert(&futex_ht, &paddr, &futex->ht_link);	254	hash_table_insert(&futex_ht, &paddr, &futex->ht_link);
251		255
252	/*	256	/*
253	* This is the first task referencing the futex.	257	* This is the first task referencing the futex.
254	* It can be directly inserted into its	258	* It can be directly inserted into its
255	* B+tree of known futexes.	259	* B+tree of known futexes.
256	*/	260	*/
257	mutex_lock(&TASK->futexes_lock);	261	mutex_lock(&TASK->futexes_lock);
258	btree_insert(&TASK->futexes, paddr, futex, NULL);	262	btree_insert(&TASK->futexes, paddr, futex, NULL);
259	mutex_unlock(&TASK->futexes_lock);	263	mutex_unlock(&TASK->futexes_lock);
260		264
261	rwlock_write_unlock(&futex_ht_lock);	265	rwlock_write_unlock(&futex_ht_lock);
262	}	266	}
263	}	267	}
264		268
265	return futex;	269	return futex;
266	}	270	}
267		271
268	/** Compute hash index into futex hash table.	272	/** Compute hash index into futex hash table.
269	*	273	*
270	* @param key Address where the key (i.e. physical address of futex counter) is stored.	274	* @param key Address where the key (i.e. physical address of futex counter) is stored.
271	*	275	*
272	* @return Index into futex hash table.	276	* @return Index into futex hash table.
273	*/	277	*/
274	index_t futex_ht_hash(__native *key)	278	index_t futex_ht_hash(__native *key)
275	{	279	{
276	return *key & (FUTEX_HT_SIZE-1);	280	return *key & (FUTEX_HT_SIZE-1);
277	}	281	}
278		282
279	/** Compare futex hash table item with a key.	283	/** Compare futex hash table item with a key.
280	*	284	*
281	* @param key Address where the key (i.e. physical address of futex counter) is stored.	285	* @param key Address where the key (i.e. physical address of futex counter) is stored.
282	*	286	*
283	* @return True if the item matches the key. False otherwise.	287	* @return True if the item matches the key. False otherwise.
284	*/	288	*/
285	bool futex_ht_compare(__native key, count_t keys, link_t item)	289	bool futex_ht_compare(__native key, count_t keys, link_t item)
286	{	290	{
287	futex_t *futex;	291	futex_t *futex;
288		292
289	ASSERT(keys == 1);	293	ASSERT(keys == 1);
290		294
291	futex = hash_table_get_instance(item, futex_t, ht_link);	295	futex = hash_table_get_instance(item, futex_t, ht_link);
292	return *key == futex->paddr;	296	return *key == futex->paddr;
293	}	297	}
294		298
295	/** Callback for removal items from futex hash table.	299	/** Callback for removal items from futex hash table.
296	*	300	*
297	* @param item Item removed from the hash table.	301	* @param item Item removed from the hash table.
298	*/	302	*/
299	void futex_ht_remove_callback(link_t *item)	303	void futex_ht_remove_callback(link_t *item)
300	{	304	{
301	futex_t *futex;	305	futex_t *futex;
302		306
303	futex = hash_table_get_instance(item, futex_t, ht_link);	307	futex = hash_table_get_instance(item, futex_t, ht_link);
304	free(futex);	308	free(futex);
305	}	309	}
306		310
307	/** Remove references from futexes known to the current task. */	311	/** Remove references from futexes known to the current task. */
308	void futex_cleanup(void)	312	void futex_cleanup(void)
309	{	313	{
310	link_t *cur;	314	link_t *cur;
311		315
312	rwlock_write_lock(&futex_ht_lock);	316	rwlock_write_lock(&futex_ht_lock);
313	mutex_lock(&TASK->futexes_lock);	317	mutex_lock(&TASK->futexes_lock);
314		318
315	for (cur = TASK->futexes.leaf_head.next; cur != &TASK->futexes.leaf_head; cur = cur->next) {	319	for (cur = TASK->futexes.leaf_head.next; cur != &TASK->futexes.leaf_head; cur = cur->next) {
316	btree_node_t *node;	320	btree_node_t *node;
317	int i;	321	int i;
318		322
319	node = list_get_instance(cur, btree_node_t, leaf_link);	323	node = list_get_instance(cur, btree_node_t, leaf_link);
320	for (i = 0; i < node->keys; i++) {	324	for (i = 0; i < node->keys; i++) {
321	futex_t *ftx;	325	futex_t *ftx;
322	__address paddr = node->key[i];	326	__address paddr = node->key[i];
323		327
324	ftx = (futex_t *) node->value[i];	328	ftx = (futex_t *) node->value[i];
325	if (--ftx->refcount == 0)	329	if (--ftx->refcount == 0)
326	hash_table_remove(&futex_ht, &paddr, 1);	330	hash_table_remove(&futex_ht, &paddr, 1);
327	}	331	}
328	}	332	}
329		333
330	mutex_unlock(&TASK->futexes_lock);	334	mutex_unlock(&TASK->futexes_lock);
331	rwlock_write_unlock(&futex_ht_lock);	335	rwlock_write_unlock(&futex_ht_lock);
332	}	336	}
-		337
-		338	/** @}
-		339	*/
-		340
333		341