Subversion Repositories HelenOS

Rev

Rev 1117 | Rev 1229 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
1109 jermar 1
/*
2
 * Copyright (C) 2006 Jakub Jermar
3
 * All rights reserved.
4
 *
5
 * Redistribution and use in source and binary forms, with or without
6
 * modification, are permitted provided that the following conditions
7
 * are met:
8
 *
9
 * - Redistributions of source code must retain the above copyright
10
 *   notice, this list of conditions and the following disclaimer.
11
 * - Redistributions in binary form must reproduce the above copyright
12
 *   notice, this list of conditions and the following disclaimer in the
13
 *   documentation and/or other materials provided with the distribution.
14
 * - The name of the author may not be used to endorse or promote products
15
 *   derived from this software without specific prior written permission.
16
 *
17
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27
 */
28
 
29
/**
30
 * Kernel backend for futexes.
31
 * Deallocation of orphaned kernel-side futex structures is not currently implemented.
32
 */
33
 
34
#include <synch/futex.h>
35
#include <synch/rwlock.h>
1117 jermar 36
#include <synch/spinlock.h>
1109 jermar 37
#include <synch/synch.h>
38
#include <mm/frame.h>
39
#include <mm/page.h>
40
#include <mm/slab.h>
1117 jermar 41
#include <proc/thread.h>
1109 jermar 42
#include <genarch/mm/page_pt.h>
43
#include <genarch/mm/page_ht.h>
44
#include <adt/hash_table.h>
45
#include <adt/list.h>
46
#include <arch.h>
47
#include <align.h>
48
#include <panic.h>
49
#include <errno.h>
50
#include <print.h>
51
 
52
#define FUTEX_HT_SIZE   1024    /* keep it a power of 2 */
53
 
54
static void futex_initialize(futex_t *futex);
55
 
1153 jermar 56
static futex_t *futex_find(__address paddr);
1109 jermar 57
static index_t futex_ht_hash(__native *key);
58
static bool futex_ht_compare(__native *key, count_t keys, link_t *item);
59
static void futex_ht_remove_callback(link_t *item);
60
 
61
/** Read-write lock protecting global futex hash table. */
62
static rwlock_t futex_ht_lock;
63
 
64
/** Futex hash table. */
65
static hash_table_t futex_ht;
66
 
67
/** Futex hash table operations. */
68
static hash_table_operations_t futex_ht_ops = {
69
    .hash = futex_ht_hash,
70
    .compare = futex_ht_compare,
71
    .remove_callback = futex_ht_remove_callback
72
};
73
 
74
/** Initialize futex subsystem. */
75
void futex_init(void)
76
{
77
    rwlock_initialize(&futex_ht_lock);
78
    hash_table_create(&futex_ht, FUTEX_HT_SIZE, 1, &futex_ht_ops);
79
}
80
 
81
/** Initialize kernel futex structure.
82
 *
83
 * @param futex Kernel futex structure.
84
 */
85
void futex_initialize(futex_t *futex)
86
{
87
    waitq_initialize(&futex->wq);
88
    link_initialize(&futex->ht_link);
89
    futex->paddr = 0;
90
}
91
 
92
/** Sleep in futex wait queue.
93
 *
94
 * @param uaddr Userspace address of the futex counter.
1117 jermar 95
 * @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.
1109 jermar 97
 *
1117 jermar 98
 * @return One of ESYNCH_TIMEOUT, ESYNCH_OK_ATOMIC and ESYNCH_OK_BLOCKED. See synch.h.
1109 jermar 99
 *     If there is no physical mapping for uaddr ENOENT is returned.
100
 */
1117 jermar 101
__native sys_futex_sleep_timeout(__address uaddr, __u32 usec, int trydown)
1109 jermar 102
{
103
    futex_t *futex;
104
    __address paddr;
105
    pte_t *t;
1117 jermar 106
    ipl_t ipl;
1109 jermar 107
 
1117 jermar 108
    ipl = interrupts_disable();
109
 
1109 jermar 110
    /*
111
     * Find physical address of futex counter.
112
     */
113
    page_table_lock(AS, true);
114
    t = page_mapping_find(AS, ALIGN_DOWN(uaddr, PAGE_SIZE));
115
    if (!t || !PTE_VALID(t) || !PTE_PRESENT(t)) {
116
        page_table_unlock(AS, true);
1117 jermar 117
        interrupts_restore(ipl);
1109 jermar 118
        return (__native) ENOENT;
119
    }
120
    paddr = PFN2ADDR(PTE_GET_FRAME(t)) + (uaddr - ALIGN_DOWN(uaddr, PAGE_SIZE));
121
    page_table_unlock(AS, true);
122
 
1117 jermar 123
    interrupts_restore(ipl);   
124
 
1153 jermar 125
    futex = futex_find(paddr);
1109 jermar 126
 
1117 jermar 127
    return (__native) waitq_sleep_timeout(&futex->wq, usec, trydown);
1109 jermar 128
}
129
 
130
/** Wakeup one thread waiting in futex wait queue.
131
 *
132
 * @param uaddr Userspace address of the futex counter.
133
 *
134
 * @return ENOENT if there is no futex associated with the address
135
 *     or if there is no physical mapping for uaddr.
136
 */
137
__native sys_futex_wakeup(__address uaddr)
138
{
1153 jermar 139
    futex_t *futex;
1109 jermar 140
    __address paddr;
141
    pte_t *t;
1117 jermar 142
    ipl_t ipl;
1109 jermar 143
 
1117 jermar 144
    ipl = interrupts_disable();
145
 
1109 jermar 146
    /*
147
     * Find physical address of futex counter.
148
     */
149
    page_table_lock(AS, true);
150
    t = page_mapping_find(AS, ALIGN_DOWN(uaddr, PAGE_SIZE));
151
    if (!t || !PTE_VALID(t) || !PTE_PRESENT(t)) {
152
        page_table_unlock(AS, true);
1117 jermar 153
        interrupts_restore(ipl);
1109 jermar 154
        return (__native) ENOENT;
155
    }
156
    paddr = PFN2ADDR(PTE_GET_FRAME(t)) + (uaddr - ALIGN_DOWN(uaddr, PAGE_SIZE));
157
    page_table_unlock(AS, true);
158
 
1117 jermar 159
    interrupts_restore(ipl);
160
 
1153 jermar 161
    futex = futex_find(paddr);
162
 
163
    waitq_wakeup(&futex->wq, WAKEUP_FIRST);
164
 
165
    return 0;
166
}
167
 
168
/** Find kernel address of the futex structure corresponding to paddr.
169
 *
170
 * If the structure does not exist alreay, a new one is created.
171
 *
172
 * @param paddr Physical address of the userspace futex counter.
173
 *
174
 * @return Address of the kernel futex structure.
175
 */
176
futex_t *futex_find(__address paddr)
177
{
178
    link_t *item;
179
    futex_t *futex;
180
 
1109 jermar 181
    /*
1153 jermar 182
     * Find the respective futex structure
183
     * or allocate new one if it does not exist already.
1109 jermar 184
     */
185
    rwlock_read_lock(&futex_ht_lock);
186
    item = hash_table_find(&futex_ht, &paddr);
187
    if (item) {
188
        futex = hash_table_get_instance(item, futex_t, ht_link);
1153 jermar 189
        rwlock_read_unlock(&futex_ht_lock);
190
    } else {
191
        /*
192
         * Upgrade to writer is not currently supported,
193
         * Therefore, it is necessary to release the read lock
194
         * and reacquire it as a writer.
195
         */
196
        rwlock_read_unlock(&futex_ht_lock);
197
 
198
        rwlock_write_lock(&futex_ht_lock);
199
        /*
200
         * Avoid possible race condition by searching
201
         * the hash table once again with write access.
202
         */
203
        item = hash_table_find(&futex_ht, &paddr);
204
        if (item) {
205
            futex = hash_table_get_instance(item, futex_t, ht_link);
206
            rwlock_write_unlock(&futex_ht_lock);
207
        } else {
208
            futex = (futex_t *) malloc(sizeof(futex_t), 0);
209
            futex_initialize(futex);
210
            futex->paddr = paddr;
211
            hash_table_insert(&futex_ht, &paddr, &futex->ht_link);
212
            rwlock_write_unlock(&futex_ht_lock);
213
        }
1109 jermar 214
    }
215
 
1153 jermar 216
    return futex;
1109 jermar 217
}
218
 
219
/** Compute hash index into futex hash table.
220
 *
221
 * @param key Address where the key (i.e. physical address of futex counter) is stored.
222
 *
223
 * @return Index into futex hash table.
224
 */
225
index_t futex_ht_hash(__native *key)
226
{
227
    return *key & (FUTEX_HT_SIZE-1);
228
}
229
 
230
/** Compare futex hash table item with a key.
231
 *
232
 * @param key Address where the key (i.e. physical address of futex counter) is stored.
233
 *
234
 * @return True if the item matches the key. False otherwise.
235
 */
236
bool futex_ht_compare(__native *key, count_t keys, link_t *item)
237
{
238
    futex_t *futex;
239
 
240
    ASSERT(keys == 1);
241
 
242
    futex = hash_table_get_instance(item, futex_t, ht_link);
243
    return *key == futex->paddr;
244
}
245
 
246
/** Callback for removal items from futex hash table.
247
 *
248
 * @param item Item removed from the hash table.
249
 */
250
void futex_ht_remove_callback(link_t *item)
251
{
252
    futex_t *futex;
253
 
254
    futex = hash_table_get_instance(item, futex_t, ht_link);
255
    free(futex);
256
}