WebSVN – HelenOS – Diff – /branches/sparc/kernel/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>
#include <arch/asm.h>
 
#define FUTEX_HT_SIZE   1024    /* keep it a power of 2 */
 
static void futex_initialize(futex_t *futex);
 
static futex_t *futex_find(uintptr_t paddr);
static index_t futex_ht_hash(unative_t *key);
static bool futex_ht_compare(unative_t *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.
 */
unative_t sys_futex_sleep_timeout(uintptr_t uaddr, uint32_t usec, int flags)
{
    futex_t *futex;
    uintptr_t paddr;
    pte_t *t;
    ipl_t ipl;
    int rc;
   
    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 (unative_t) ENOENT;
    }
    paddr = PTE_GET_FRAME(t) + (uaddr - ALIGN_DOWN(uaddr, PAGE_SIZE));
    page_table_unlock(AS, true);
   
    interrupts_restore(ipl);   
 
    futex = futex_find(paddr);
 
#ifdef CONFIG_UDEBUG
    udebug_stoppable_begin();
#endif
    rc = waitq_sleep_timeout(&futex->wq, usec, flags |
        SYNCH_FLAGS_INTERRUPTIBLE);
 
#ifdef CONFIG_UDEBUG
    udebug_stoppable_end();
#endif
    return (unative_t) rc;
}
 
/** 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.
 */
unative_t sys_futex_wakeup(uintptr_t uaddr)
{
    futex_t *futex;
    uintptr_t 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 (unative_t) 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(uintptr_t 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(unative_t *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(unative_t *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;
        unsigned int i;
       
        node = list_get_instance(cur, btree_node_t, leaf_link);
        for (i = 0; i < node->keys; i++) {
            futex_t *ftx;
            uintptr_t 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);
}
 
/** @}
 */
 

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

Subversion Repositories HelenOS

(root)/branches/sparc/kernel/generic/src/synch/futex.c – Rev 3665 → 3862