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.
 */
 
/**
 * @file    futex.c
 * @brief   Kernel backend for futexes.
 *
 * @todo Deallocation of orphaned kernel-side futex structures is not currently implemented.
 */
 
#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 <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. */
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;
}
 
/** 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 trydown If usec is zero and trydown is non-zero, conditional operation will be attempted.
 *
 * @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 trydown)
{
    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 = PFN2ADDR(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, trydown);
}
 
/** Wakeup one thread waiting in futex wait queue.
 *
 * @param uaddr Userspace address of the futex counter.
 *
 * @return ENOENT if there is no futex associated with the address
 *     or 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 = PFN2ADDR(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 alreay, 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;
   
    /*
     * 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);
        rwlock_read_unlock(&futex_ht_lock);
    } else {
        /*
         * 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);
            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);
            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);
}
 

Subversion Repositories HelenOS-historic

(root)/kernel/trunk/generic/src/synch/futex.c @ 1757 – Rev 1248 → 1264

Rev 1248		Rev 1264
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	/**	29	/**
-		30	* @file futex.c
30	* Kernel backend for futexes.	31	* @brief Kernel backend for futexes.
-		32	*
31	* Deallocation of orphaned kernel-side futex structures is not currently implemented.	33	* @todo Deallocation of orphaned kernel-side futex structures is not currently implemented.
32	*/	34	*/
33		35
34	#include <synch/futex.h>	36	#include <synch/futex.h>
35	#include <synch/rwlock.h>	37	#include <synch/rwlock.h>
36	#include <synch/spinlock.h>	38	#include <synch/spinlock.h>
37	#include <synch/synch.h>	39	#include <synch/synch.h>
38	#include <mm/frame.h>	40	#include <mm/frame.h>
39	#include <mm/page.h>	41	#include <mm/page.h>
40	#include <mm/slab.h>	42	#include <mm/slab.h>
41	#include <proc/thread.h>	43	#include <proc/thread.h>
42	#include <genarch/mm/page_pt.h>	44	#include <genarch/mm/page_pt.h>
43	#include <genarch/mm/page_ht.h>	45	#include <genarch/mm/page_ht.h>
44	#include <adt/hash_table.h>	46	#include <adt/hash_table.h>
45	#include <adt/list.h>	47	#include <adt/list.h>
46	#include <arch.h>	48	#include <arch.h>
47	#include <align.h>	49	#include <align.h>
48	#include <panic.h>	50	#include <panic.h>
49	#include <errno.h>	51	#include <errno.h>
50	#include <print.h>	52	#include <print.h>
51		53
52	#define FUTEX_HT_SIZE 1024 /* keep it a power of 2 */	54	#define FUTEX_HT_SIZE 1024 /* keep it a power of 2 */
53		55
54	static void futex_initialize(futex_t *futex);	56	static void futex_initialize(futex_t *futex);
55		57
56	static futex_t *futex_find(__address paddr);	58	static futex_t *futex_find(__address paddr);
57	static index_t futex_ht_hash(__native *key);	59	static index_t futex_ht_hash(__native *key);
58	static bool futex_ht_compare(__native key, count_t keys, link_t item);	60	static bool futex_ht_compare(__native key, count_t keys, link_t item);
59	static void futex_ht_remove_callback(link_t *item);	61	static void futex_ht_remove_callback(link_t *item);
60		62
61	/** Read-write lock protecting global futex hash table. */	63	/** Read-write lock protecting global futex hash table. */
62	static rwlock_t futex_ht_lock;	64	static rwlock_t futex_ht_lock;
63		65
64	/** Futex hash table. */	66	/** Futex hash table. */
65	static hash_table_t futex_ht;	67	static hash_table_t futex_ht;
66		68
67	/** Futex hash table operations. */	69	/** Futex hash table operations. */
68	static hash_table_operations_t futex_ht_ops = {	70	static hash_table_operations_t futex_ht_ops = {
69	.hash = futex_ht_hash,	71	.hash = futex_ht_hash,
70	.compare = futex_ht_compare,	72	.compare = futex_ht_compare,
71	.remove_callback = futex_ht_remove_callback	73	.remove_callback = futex_ht_remove_callback
72	};	74	};
73		75
74	/** Initialize futex subsystem. */	76	/** Initialize futex subsystem. */
75	void futex_init(void)	77	void futex_init(void)
76	{	78	{
77	rwlock_initialize(&futex_ht_lock);	79	rwlock_initialize(&futex_ht_lock);
78	hash_table_create(&futex_ht, FUTEX_HT_SIZE, 1, &futex_ht_ops);	80	hash_table_create(&futex_ht, FUTEX_HT_SIZE, 1, &futex_ht_ops);
79	}	81	}
80		82
81	/** Initialize kernel futex structure.	83	/** Initialize kernel futex structure.
82	*	84	*
83	* @param futex Kernel futex structure.	85	* @param futex Kernel futex structure.
84	*/	86	*/
85	void futex_initialize(futex_t *futex)	87	void futex_initialize(futex_t *futex)
86	{	88	{
87	waitq_initialize(&futex->wq);	89	waitq_initialize(&futex->wq);
88	link_initialize(&futex->ht_link);	90	link_initialize(&futex->ht_link);
89	futex->paddr = 0;	91	futex->paddr = 0;
90	}	92	}
91		93
92	/** Sleep in futex wait queue.	94	/** Sleep in futex wait queue.
93	*	95	*
94	* @param uaddr Userspace address of the futex counter.	96	* @param uaddr Userspace address of the futex counter.
95	* @param usec If non-zero, number of microseconds this thread is willing to sleep.	97	* @param usec If non-zero, number of microseconds this thread is willing to sleep.
96	* @param trydown If usec is zero and trydown is non-zero, conditional operation will be attempted.	98	* @param trydown If usec is zero and trydown is non-zero, conditional operation will be attempted.
97	*	99	*
98	* @return One of ESYNCH_TIMEOUT, ESYNCH_OK_ATOMIC and ESYNCH_OK_BLOCKED. See synch.h.	100	* @return One of ESYNCH_TIMEOUT, ESYNCH_OK_ATOMIC and ESYNCH_OK_BLOCKED. See synch.h.
99	* If there is no physical mapping for uaddr ENOENT is returned.	101	* If there is no physical mapping for uaddr ENOENT is returned.
100	*/	102	*/
101	__native sys_futex_sleep_timeout(__address uaddr, __u32 usec, int trydown)	103	__native sys_futex_sleep_timeout(__address uaddr, __u32 usec, int trydown)
102	{	104	{
103	futex_t *futex;	105	futex_t *futex;
104	__address paddr;	106	__address paddr;
105	pte_t *t;	107	pte_t *t;
106	ipl_t ipl;	108	ipl_t ipl;
107		109
108	ipl = interrupts_disable();	110	ipl = interrupts_disable();
109		111
110	/*	112	/*
111	* Find physical address of futex counter.	113	* Find physical address of futex counter.
112	*/	114	*/
113	page_table_lock(AS, true);	115	page_table_lock(AS, true);
114	t = page_mapping_find(AS, ALIGN_DOWN(uaddr, PAGE_SIZE));	116	t = page_mapping_find(AS, ALIGN_DOWN(uaddr, PAGE_SIZE));
115	if (!t \|\| !PTE_VALID(t) \|\| !PTE_PRESENT(t)) {	117	if (!t \|\| !PTE_VALID(t) \|\| !PTE_PRESENT(t)) {
116	page_table_unlock(AS, true);	118	page_table_unlock(AS, true);
117	interrupts_restore(ipl);	119	interrupts_restore(ipl);
118	return (__native) ENOENT;	120	return (__native) ENOENT;
119	}	121	}
120	paddr = PFN2ADDR(PTE_GET_FRAME(t)) + (uaddr - ALIGN_DOWN(uaddr, PAGE_SIZE));	122	paddr = PFN2ADDR(PTE_GET_FRAME(t)) + (uaddr - ALIGN_DOWN(uaddr, PAGE_SIZE));
121	page_table_unlock(AS, true);	123	page_table_unlock(AS, true);
122		124
123	interrupts_restore(ipl);	125	interrupts_restore(ipl);
124		126
125	futex = futex_find(paddr);	127	futex = futex_find(paddr);
126		128
127	return (__native) waitq_sleep_timeout(&futex->wq, usec, trydown);	129	return (__native) waitq_sleep_timeout(&futex->wq, usec, trydown);
128	}	130	}
129		131
130	/** Wakeup one thread waiting in futex wait queue.	132	/** Wakeup one thread waiting in futex wait queue.
131	*	133	*
132	* @param uaddr Userspace address of the futex counter.	134	* @param uaddr Userspace address of the futex counter.
133	*	135	*
134	* @return ENOENT if there is no futex associated with the address	136	* @return ENOENT if there is no futex associated with the address
135	* or if there is no physical mapping for uaddr.	137	* or if there is no physical mapping for uaddr.
136	*/	138	*/
137	__native sys_futex_wakeup(__address uaddr)	139	__native sys_futex_wakeup(__address uaddr)
138	{	140	{
139	futex_t *futex;	141	futex_t *futex;
140	__address paddr;	142	__address paddr;
141	pte_t *t;	143	pte_t *t;
142	ipl_t ipl;	144	ipl_t ipl;
143		145
144	ipl = interrupts_disable();	146	ipl = interrupts_disable();
145		147
146	/*	148	/*
147	* Find physical address of futex counter.	149	* Find physical address of futex counter.
148	*/	150	*/
149	page_table_lock(AS, true);	151	page_table_lock(AS, true);
150	t = page_mapping_find(AS, ALIGN_DOWN(uaddr, PAGE_SIZE));	152	t = page_mapping_find(AS, ALIGN_DOWN(uaddr, PAGE_SIZE));
151	if (!t \|\| !PTE_VALID(t) \|\| !PTE_PRESENT(t)) {	153	if (!t \|\| !PTE_VALID(t) \|\| !PTE_PRESENT(t)) {
152	page_table_unlock(AS, true);	154	page_table_unlock(AS, true);
153	interrupts_restore(ipl);	155	interrupts_restore(ipl);
154	return (__native) ENOENT;	156	return (__native) ENOENT;
155	}	157	}
156	paddr = PFN2ADDR(PTE_GET_FRAME(t)) + (uaddr - ALIGN_DOWN(uaddr, PAGE_SIZE));	158	paddr = PFN2ADDR(PTE_GET_FRAME(t)) + (uaddr - ALIGN_DOWN(uaddr, PAGE_SIZE));
157	page_table_unlock(AS, true);	159	page_table_unlock(AS, true);
158		160
159	interrupts_restore(ipl);	161	interrupts_restore(ipl);
160		162
161	futex = futex_find(paddr);	163	futex = futex_find(paddr);
162		164
163	waitq_wakeup(&futex->wq, WAKEUP_FIRST);	165	waitq_wakeup(&futex->wq, WAKEUP_FIRST);
164		166
165	return 0;	167	return 0;
166	}	168	}
167		169
168	/** Find kernel address of the futex structure corresponding to paddr.	170	/** Find kernel address of the futex structure corresponding to paddr.
169	*	171	*
170	* If the structure does not exist alreay, a new one is created.	172	* If the structure does not exist alreay, a new one is created.
171	*	173	*
172	* @param paddr Physical address of the userspace futex counter.	174	* @param paddr Physical address of the userspace futex counter.
173	*	175	*
174	* @return Address of the kernel futex structure.	176	* @return Address of the kernel futex structure.
175	*/	177	*/
176	futex_t *futex_find(__address paddr)	178	futex_t *futex_find(__address paddr)
177	{	179	{
178	link_t *item;	180	link_t *item;
179	futex_t *futex;	181	futex_t *futex;
180		182
181	/*	183	/*
182	* Find the respective futex structure	184	* Find the respective futex structure
183	* or allocate new one if it does not exist already.	185	* or allocate new one if it does not exist already.
184	*/	186	*/
185	rwlock_read_lock(&futex_ht_lock);	187	rwlock_read_lock(&futex_ht_lock);
186	item = hash_table_find(&futex_ht, &paddr);	188	item = hash_table_find(&futex_ht, &paddr);
187	if (item) {	189	if (item) {
188	futex = hash_table_get_instance(item, futex_t, ht_link);	190	futex = hash_table_get_instance(item, futex_t, ht_link);
189	rwlock_read_unlock(&futex_ht_lock);	191	rwlock_read_unlock(&futex_ht_lock);
190	} else {	192	} else {
191	/*	193	/*
192	* Upgrade to writer is not currently supported,	194	* Upgrade to writer is not currently supported,
193	* Therefore, it is necessary to release the read lock	195	* Therefore, it is necessary to release the read lock
194	* and reacquire it as a writer.	196	* and reacquire it as a writer.
195	*/	197	*/
196	rwlock_read_unlock(&futex_ht_lock);	198	rwlock_read_unlock(&futex_ht_lock);
197		199
198	rwlock_write_lock(&futex_ht_lock);	200	rwlock_write_lock(&futex_ht_lock);
199	/*	201	/*
200	* Avoid possible race condition by searching	202	* Avoid possible race condition by searching
201	* the hash table once again with write access.	203	* the hash table once again with write access.
202	*/	204	*/
203	item = hash_table_find(&futex_ht, &paddr);	205	item = hash_table_find(&futex_ht, &paddr);
204	if (item) {	206	if (item) {
205	futex = hash_table_get_instance(item, futex_t, ht_link);	207	futex = hash_table_get_instance(item, futex_t, ht_link);
206	rwlock_write_unlock(&futex_ht_lock);	208	rwlock_write_unlock(&futex_ht_lock);
207	} else {	209	} else {
208	futex = (futex_t *) malloc(sizeof(futex_t), 0);	210	futex = (futex_t *) malloc(sizeof(futex_t), 0);
209	futex_initialize(futex);	211	futex_initialize(futex);
210	futex->paddr = paddr;	212	futex->paddr = paddr;
211	hash_table_insert(&futex_ht, &paddr, &futex->ht_link);	213	hash_table_insert(&futex_ht, &paddr, &futex->ht_link);
212	rwlock_write_unlock(&futex_ht_lock);	214	rwlock_write_unlock(&futex_ht_lock);
213	}	215	}
214	}	216	}
215		217
216	return futex;	218	return futex;
217	}	219	}
218		220
219	/** Compute hash index into futex hash table.	221	/** Compute hash index into futex hash table.
220	*	222	*
221	* @param key Address where the key (i.e. physical address of futex counter) is stored.	223	* @param key Address where the key (i.e. physical address of futex counter) is stored.
222	*	224	*
223	* @return Index into futex hash table.	225	* @return Index into futex hash table.
224	*/	226	*/
225	index_t futex_ht_hash(__native *key)	227	index_t futex_ht_hash(__native *key)
226	{	228	{
227	return *key & (FUTEX_HT_SIZE-1);	229	return *key & (FUTEX_HT_SIZE-1);
228	}	230	}
229		231
230	/** Compare futex hash table item with a key.	232	/** Compare futex hash table item with a key.
231	*	233	*
232	* @param key Address where the key (i.e. physical address of futex counter) is stored.	234	* @param key Address where the key (i.e. physical address of futex counter) is stored.
233	*	235	*
234	* @return True if the item matches the key. False otherwise.	236	* @return True if the item matches the key. False otherwise.
235	*/	237	*/
236	bool futex_ht_compare(__native key, count_t keys, link_t item)	238	bool futex_ht_compare(__native key, count_t keys, link_t item)
237	{	239	{
238	futex_t *futex;	240	futex_t *futex;
239		241
240	ASSERT(keys == 1);	242	ASSERT(keys == 1);
241		243
242	futex = hash_table_get_instance(item, futex_t, ht_link);	244	futex = hash_table_get_instance(item, futex_t, ht_link);
243	return *key == futex->paddr;	245	return *key == futex->paddr;
244	}	246	}
245		247
246	/** Callback for removal items from futex hash table.	248	/** Callback for removal items from futex hash table.
247	*	249	*
248	* @param item Item removed from the hash table.	250	* @param item Item removed from the hash table.
249	*/	251	*/
250	void futex_ht_remove_callback(link_t *item)	252	void futex_ht_remove_callback(link_t *item)
251	{	253	{
252	futex_t *futex;	254	futex_t *futex;
253		255
254	futex = hash_table_get_instance(item, futex_t, ht_link);	256	futex = hash_table_get_instance(item, futex_t, ht_link);
255	free(futex);	257	free(futex);
256	}	258	}
257		259