[RFC] kern: simple futex for gnumach (version 5)
Number of threads to wake is now a boolean, which means it's one or all.
Call to assert_wait() has been added before thread_suspend(). The scan
for vm_objects has been removed and recursion in futex_wake() has been
removed and code rewriten.
There are problems however, futex_wait() test on the Hurd fails with
illegal instruction error. When I comment out the entire futex_wait()
I still get the same error, so I don't know how to fix this, since
I can't trace the error to any instruction in the program. The code
to reproduce this is:
extern int futex_wait();
int e = 0;
int main(void)
{
return futex_wait(e, e);
}
On Linux everything works fine, except segfaults in vm_map_lookup() and
assert_wait() and of course thread_suspend() doesn't actually work. But
when commented out everything else works fine.
There is also a failed assertion in malloc.c:3096 when allocating memory
for the threads.
If anybody has any info on this errors, I'll be thankful. They may just
be beginner's mistakes.
---
Makefrag.am |2 +
kern/futex.c | 370 ++
kern/futex.h | 100
3 files changed, 472 insertions(+)
create mode 100644 kern/futex.c
create mode 100644 kern/futex.h
diff --git a/Makefrag.am b/Makefrag.am
index c1387bd..e43f882 100644
--- a/Makefrag.am
+++ b/Makefrag.am
@@ -145,6 +145,8 @@ libkernel_a_SOURCES += \
kern/eventcount.h \
kern/exception.c \
kern/exception.h \
+ kern/futex.c \
+ kern/futex.h \
kern/host.c \
kern/host.h \
kern/ipc_host.c \
diff --git a/kern/futex.c b/kern/futex.c
new file mode 100644
index 000..878be81
--- /dev/null
+++ b/kern/futex.c
@@ -0,0 +1,370 @@
+/*
+ * Copyright (C) 2013 Free Software Foundation, Inc.
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2, or (at your option)
+ * any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
+ *
+ * Author: Marin Ramesa
+ */
+
+/*
+ * Fast userspace locking
+ *
+ */
+
+#include kern/futex.h
+#include kern/sched_prim.h
+
+static futex_hash_table_t table = NULL;
+static unsigned int prev_hash_val = 0;
+static unsigned int max_hash_val = 0;
+
+/*
+ * When operation equals futex_wait(), this is a method for a thread to wait
for a
+ * change of value at a given address.
+ *
+ * When operation equals futex_wake(), this is a method for waking up all or
one
+ * thread waiting for a change of value at a given address.
+ *
+ * Return values:
+ * FUTEX_RESUMED_BY_WAKE - thread has been resumed by futex_wake()
+ * FUTEX_NO_THREAD_SUSPENDED - value at the address has been changed while
inside
+ * futex_wait() and no thread has been suspended
+ * FUTEX_SOME_NUMBER_RESUMED - threads have been resumed by futex_wake()
+ * FUTEX_NO_THREAD - futex_wake() did not found a suspended thread at the
passed address
+ * FUTEX_MEMORY_ERROR - memory error
+ * FUTEX_RESOURCE_SHORTAGE - no virtual memory
+ * FUTEX_THREAD_NO_SUSPEND - thread suspend failed
+ *
+ */
+
+int futex_init(futex_t futex, int *address)
+{
+ if (table == NULL) {
+ if (futex_hash_table_init() == FUTEX_RESOURCE_SHORTAGE)
+ return FUTEX_RESOURCE_SHORTAGE;
+ }
+
+ if ((table-futex_elements =
(futex_t)__builtin_malloc((max_hash_val+1)*sizeof(struct futex))) == NULL)
+ return FUTEX_RESOURCE_SHORTAGE;
+
+ simple_lock_init(futex-futex_wait_lock);
+
+ futex-address = address;
+ futex-num_futexed_threads = 0;
+ futex-next_futex = NULL;
+ futex-prev_futex = (table-futex_elements[prev_hash_val]);
+ futex-prev_futex-next_futex = futex;
+ *futex-map = current_thread()-task-map;
+
+ if ((vm_map_lookup(futex-map, (vm_offset_t)address, VM_PROT_READ,
futex-version, futex-object,
+ futex-offset, futex-out_prot, futex-wired)
!= KERN_SUCCESS)) {
+ unsigned int temp_hash_val = futex_hash(address);
+ __builtin_free((table-futex_elements[temp_hash_val]));
+ return FUTEX_MEMORY_ERROR;
+ }
+
+ return 0;
+}
+
+int futex_wait(int *address, int value)
+{
+ futex_t futex;
+
+ lookup:
+
+ futex = futex_hash_table_lookup_address(address);
+
+ if (futex != NULL) {
+
+ simple_lock(futex-futex_wait_lock);
+
+ /* If the
Re: [RFC] kern: simple futex for gnumach (version 5)
On Thu, Dec 26, 2013 at 02:30:10PM +0100, Marin Ramesa wrote:
+ futex-address = address;
+ futex-num_futexed_threads = 0;
+ futex-next_futex = NULL;
+ futex-prev_futex = (table-futex_elements[prev_hash_val]);
+ futex-prev_futex-next_futex = futex;
+ *futex-map = current_thread()-task-map;
A futex shouldn't be a task-local object since it's used for inter
process synchronization. There should be per-thread objects (probably
allocated on the stack since a thread can only be doing one wait at
a time), and these per-thread objects should be listed in the global
futex object. Waking up the futex then simply walks the list and wakes
up threads.
+ if ((vm_map_lookup(futex-map, (vm_offset_t)address, VM_PROT_READ,
futex-version, futex-object,
+ futex-offset, futex-out_prot, futex-wired)
!= KERN_SUCCESS)) {
+ unsigned int temp_hash_val = futex_hash(address);
+ __builtin_free((table-futex_elements[temp_hash_val]));
Why __builtin_malloc and __builtin_free ??
+ if (futex-num_futexed_threads == 128)
+ return FUTEX_RESOURCE_SHORTAGE;
I assume this limit is temporary. If not, remove it, there is no reason
to add a constraint like this one.
+ suspend:
+ assert_wait(current_thread()-state , FALSE);
+ simple_unlock(futex-futex_wait_lock);
+ kern_return_t ret = thread_suspend(current_thread());
I really doubt assert_wait can be used with thread_suspend and
thread_resume... Use thread_block and thread_wakeup instead. Again, be
more careful.
+struct futex {
As previously said, rework that structure.
+ /* Next futex in queue. */
+ futex_t next_futex;
+
+ /* Previous futex in queue. */
+ futex_t prev_futex;
Do NOT reimplement generic doubly-linked lists...
+ /* Number of futexed threads at the same address. */
+ unsigned int num_futexed_threads;
+
+ /* Array of futexed threads at the same address. */
+ //thread_t futexed_threads;
+
+ thread_t futexed_threads[128];
Ugh. No.
+int futex_init(futex_t futex, int *address);
+extern int futex_wait(int *address, int value);
+extern int futex_wake(int *address, boolean_t wake_all);
+void futex_cross_address_space_wake(futex_t futex, boolean_t wake_all);
+void futex_wake_threads(futex_t futex, boolean_t wake_all);
+int futex_hash_table_init(void);
+unsigned int futex_hash(int *address);
+futex_t futex_hash_table_lookup_address(int *address);
+int futex_hash_table_add_address(int *address);
+void futex_hash_table_delete_futex(futex_t futex);
I know this isn't the traditional way to do it in Mach, but please,
extensively document the API in the header, e.g. as it's done for the
slab allocator. I also suggest moving everything not public (such as
the hash table) in the .c file, and if there is anything private that
still needs to be in a header, move that to a _i.h file (i could mean
internal/implementation/inline/whatever), so that the main header only
documents the public API.
--
Richard Braun
Re: [RFC] kern: simple futex for gnumach (version 5)
On Thu, Dec 26, 2013 at 02:58:01PM +0100, Richard Braun wrote: I know this isn't the traditional way to do it in Mach, but please, extensively document the API in the header, e.g. as it's done for the slab allocator. I also suggest moving everything not public (such as Actually, kern/rbtree.h is a better example concerning the separation of private/public stuff. -- Richard Braun
Re: [RFC] kern: simple futex for gnumach (version 5)
On 12/26/2013 02:58:01 PM, Richard Braun wrote: Why __builtin_malloc and __builtin_free ?? I get segfaults in kalloc(). I don't know what I'm doing wrong. + if (futex-num_futexed_threads == 128) + return FUTEX_RESOURCE_SHORTAGE; I assume this limit is temporary. If not, remove it, there is no reason to add a constraint like this one. This is just for testing until I found a dynamic allocation function that I can use with thread allocation. Thanks for the comments!
Re: [RFC] kern: simple futex for gnumach (version 5)
On Thu, Dec 26, 2013 at 03:15:24PM +0100, Marin Ramesa wrote: I get segfaults in kalloc(). I don't know what I'm doing wrong. Show us how you use it. -- Richard Braun
Re: [RFC] kern: simple futex for gnumach (version 5)
On 12/26/2013 03:25:11 PM, Richard Braun wrote: On Thu, Dec 26, 2013 at 03:15:24PM +0100, Marin Ramesa wrote: I get segfaults in kalloc(). I don't know what I'm doing wrong. Show us how you use it. futex-futexed_threads = (thread_t)kalloc((futex-num_futexed_threads+1)*sizeof(struct thread)); When futexed_threads is a pointer to struct thread.
Re: [RFC] kern: simple futex for gnumach (version 5)
On Thu, Dec 26, 2013 at 03:51:30PM +0100, Marin Ramesa wrote: futex-futexed_threads = (thread_t)kalloc((futex-num_futexed_threads+1)*sizeof(struct thread)); When futexed_threads is a pointer to struct thread. Why are you allocating a thread structure ?? I strongly suspect kalloc does what you want it to do, but something in your code makes an illegal access. In the worst case, use prints to find the faulty instruction. -- Richard Braun
