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.
 
 
 */
 
#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 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 = 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 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);
}
 

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

Subversion Repositories HelenOS-historic

(root)/kernel/trunk/generic/src/synch/futex.c – Rev 1414 → 1460