← Back to branch summary

~martin-decky/helenos/rcu

« back to all changes in this revision

Viewing changes to kernel/generic/src/synch/futex.c

  • Committer: Martin Decky
  • Date: 2009-08-04 11:19:19 UTC
  • Revision ID: martin@uranus.dsrg.hide.ms.mff.cuni.cz-20090804111919-evyclddlr3v5lhmp
Initial import

Show diffs side-by-side

added added

removed removed

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