From c178f7199d7070c5481c5f0f3077f8dcbfa90226 Mon Sep 17 00:00:00 2001 From: Slendi Date: Thu, 15 Feb 2024 15:51:28 +0200 Subject: Get Odin to compile on Haiku This patch makes Odin to compile on Haiku which is a good first step. Now, all that's needed to do is to figure out how to do futexes, which I am blaming for the program crashing. --- src/threading.cpp | 47 ++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 46 insertions(+), 1 deletion(-) (limited to 'src/threading.cpp') diff --git a/src/threading.cpp b/src/threading.cpp index 725b58c89..ea987890b 100644 --- a/src/threading.cpp +++ b/src/threading.cpp @@ -831,8 +831,53 @@ gb_internal void futex_wait(Futex *f, Footex val) { WaitOnAddress(f, (void *)&val, sizeof(val), INFINITE); } while (f->load() == val); } +#elif defined(GB_SYSTEM_HAIKU) + +#include +#include +#include + +struct MutexCond { + pthread_mutex_t mutex; + pthread_cond_t cond; +}; + +std::unordered_map> futex_map; + +MutexCond* get_mutex_cond(Futex* f) { + if (futex_map.find(f) == futex_map.end()) { + futex_map[f] = std::make_unique(); + pthread_mutex_init(&futex_map[f]->mutex, NULL); + pthread_cond_init(&futex_map[f]->cond, NULL); + } + return futex_map[f].get(); +} + +void futex_signal(Futex *f) { + MutexCond* mc = get_mutex_cond(f); + pthread_mutex_lock(&mc->mutex); + pthread_cond_signal(&mc->cond); + pthread_mutex_unlock(&mc->mutex); +} + +void futex_broadcast(Futex *f) { + MutexCond* mc = get_mutex_cond(f); + pthread_mutex_lock(&mc->mutex); + pthread_cond_broadcast(&mc->cond); + pthread_mutex_unlock(&mc->mutex); +} + +void futex_wait(Futex *f, Footex val) { + MutexCond* mc = get_mutex_cond(f); + pthread_mutex_lock(&mc->mutex); + while (f->load() == val) { + pthread_cond_wait(&mc->cond, &mc->mutex); + } + pthread_mutex_unlock(&mc->mutex); +} + #endif #if defined(GB_SYSTEM_WINDOWS) #pragma warning(pop) -#endif \ No newline at end of file +#endif -- cgit v1.2.3 From 824c831190da1efc351de38743876376a5bb1b08 Mon Sep 17 00:00:00 2001 From: avanspector Date: Sat, 24 Feb 2024 23:46:55 +0100 Subject: Implement futex --- src/threading.cpp | 132 ++++++++++++++++++++++++++++++++++++++++-------------- 1 file changed, 99 insertions(+), 33 deletions(-) (limited to 'src/threading.cpp') diff --git a/src/threading.cpp b/src/threading.cpp index ea987890b..1805e51e2 100644 --- a/src/threading.cpp +++ b/src/threading.cpp @@ -831,49 +831,115 @@ gb_internal void futex_wait(Futex *f, Footex val) { WaitOnAddress(f, (void *)&val, sizeof(val), INFINITE); } while (f->load() == val); } + #elif defined(GB_SYSTEM_HAIKU) -#include -#include -#include +// Futex implementation taken from https://tavianator.com/2023/futex.html -struct MutexCond { - pthread_mutex_t mutex; - pthread_cond_t cond; +#include +#include + +struct Futex_Wait_Node { + pthread_t thread; + Futex *futex; + Futex_Wait_Node *prev, *next; }; - -std::unordered_map> futex_map; - -MutexCond* get_mutex_cond(Futex* f) { - if (futex_map.find(f) == futex_map.end()) { - futex_map[f] = std::make_unique(); - pthread_mutex_init(&futex_map[f]->mutex, NULL); - pthread_cond_init(&futex_map[f]->cond, NULL); + +struct Futex_Wait_Queue { + std::atomic_flag spinlock; + Futex_Wait_Node list; + + void lock() { + while (spinlock.test_and_set(std::memory_order_acquire)) { + ; // spin... + } + } + + void unlock() { + spinlock.clear(std::memory_order_release); } - return futex_map[f].get(); -} +}; +// FIXME: This approach may scale badly in the future, +// possible solution - hash map (leads to deadlocks now). + +Futex_Wait_Queue g_waitq = { + .spinlock = ATOMIC_FLAG_INIT, + .list = { + .prev = &g_waitq.list, + .next = &g_waitq.list, + }, +}; + +Futex_Wait_Queue *get_wait_queue(Futex *f) { + // Future hash map method... + return &g_waitq; +} + void futex_signal(Futex *f) { - MutexCond* mc = get_mutex_cond(f); - pthread_mutex_lock(&mc->mutex); - pthread_cond_signal(&mc->cond); - pthread_mutex_unlock(&mc->mutex); + auto waitq = get_wait_queue(f); + + waitq->lock(); + + auto head = &waitq->list; + for (auto waiter = head->next; waiter != head; waiter = waiter->next) { + if (waiter->futex == f) { + pthread_kill(waiter->thread, SIGCONT); + break; + } + } + + waitq->unlock(); } - + void futex_broadcast(Futex *f) { - MutexCond* mc = get_mutex_cond(f); - pthread_mutex_lock(&mc->mutex); - pthread_cond_broadcast(&mc->cond); - pthread_mutex_unlock(&mc->mutex); -} - + auto waitq = get_wait_queue(f); + + waitq->lock(); + + auto head = &waitq->list; + for (auto waiter = head->next; waiter != head; waiter = waiter->next) { + if (waiter->futex == f) { + pthread_kill(waiter->thread, SIGCONT); + } + } + + waitq->unlock(); +} + void futex_wait(Futex *f, Footex val) { - MutexCond* mc = get_mutex_cond(f); - pthread_mutex_lock(&mc->mutex); - while (f->load() == val) { - pthread_cond_wait(&mc->cond, &mc->mutex); - } - pthread_mutex_unlock(&mc->mutex); + auto waitq = get_wait_queue(f); + + waitq->lock(); + + auto head = &waitq->list; + Wait_Node waiter; + waiter.thread = pthread_self(); + waiter.futex = f; + waiter.prev = head; + waiter.next = head->next; + + waiter.prev->next = &waiter; + waiter.next->prev = &waiter; + + sigset_t old_mask, mask; + sigemptyset(&mask); + sigaddset(&mask, SIGCONT); + pthread_sigmask(SIG_BLOCK, &mask, &old_mask); + + if (*f == val) { + waitq->unlock(); + int sig; + sigwait(&mask, &sig); + waitq->lock(); + } + + waiter.prev->next = waiter.next; + waiter.next->prev = waiter.prev; + + pthread_sigmask(SIG_SETMASK, &old_mask, NULL); + + waitq->unlock(); } #endif -- cgit v1.2.3 From 028a79e66c714180852c94db165de3aaa97c1df8 Mon Sep 17 00:00:00 2001 From: avanspector Date: Sun, 25 Feb 2024 02:34:41 +0100 Subject: Update threading.cpp --- src/threading.cpp | 2 ++ 1 file changed, 2 insertions(+) (limited to 'src/threading.cpp') diff --git a/src/threading.cpp b/src/threading.cpp index 1805e51e2..6602bf67e 100644 --- a/src/threading.cpp +++ b/src/threading.cpp @@ -492,6 +492,8 @@ gb_internal u32 thread_current_id(void) { __asm__("mov %%fs:0x10,%0" : "=r"(thread_id)); #elif defined(GB_SYSTEM_LINUX) thread_id = gettid(); +#elif defined(GB_SYSTEM_HAIKU) + thread_id = find_thread(NULL); #else #error Unsupported architecture for thread_current_id() #endif -- cgit v1.2.3 From 24c8b1540920bd181dc399bf86f2ec3a8ea72762 Mon Sep 17 00:00:00 2001 From: avanspector Date: Sun, 25 Feb 2024 02:38:35 +0100 Subject: small fixes --- src/build_settings.cpp | 2 ++ src/threading.cpp | 2 +- 2 files changed, 3 insertions(+), 1 deletion(-) (limited to 'src/threading.cpp') diff --git a/src/build_settings.cpp b/src/build_settings.cpp index f395cb515..e4e360270 100644 --- a/src/build_settings.cpp +++ b/src/build_settings.cpp @@ -885,6 +885,8 @@ gb_internal String internal_odin_root_dir(void) { #include +gb_internal String path_to_fullpath(gbAllocator a, String s, bool *ok_); + gb_internal String internal_odin_root_dir(void) { String path = global_module_path; isize len, i; diff --git a/src/threading.cpp b/src/threading.cpp index 6602bf67e..56f246955 100644 --- a/src/threading.cpp +++ b/src/threading.cpp @@ -915,7 +915,7 @@ void futex_wait(Futex *f, Footex val) { waitq->lock(); auto head = &waitq->list; - Wait_Node waiter; + Futex_Wait_Node waiter; waiter.thread = pthread_self(); waiter.futex = f; waiter.prev = head; -- cgit v1.2.3 From d4d9f55556ffa71e519ffcc5df431edc097746e2 Mon Sep 17 00:00:00 2001 From: avanspector Date: Fri, 1 Mar 2024 00:41:28 +0100 Subject: Update threading.cpp --- src/threading.cpp | 145 ++++++++++++++++++++++++++++++++++++++---------------- 1 file changed, 102 insertions(+), 43 deletions(-) (limited to 'src/threading.cpp') diff --git a/src/threading.cpp b/src/threading.cpp index 56f246955..a469435d2 100644 --- a/src/threading.cpp +++ b/src/threading.cpp @@ -840,86 +840,131 @@ gb_internal void futex_wait(Futex *f, Footex val) { #include #include + +struct _Spinlock { + std::atomic_flag state; + + void init() { + state.clear(); + } + + void lock() { + while (state.test_and_set(std::memory_order_acquire)) { + #if defined(GB_CPU_X86) + _mm_pause(); + #else + (void)0; // spin... + #endif + } + } + + void unlock() { + state.clear(std::memory_order_release); + } +}; + +struct Futex_Waitq; -struct Futex_Wait_Node { +struct Futex_Waiter { + _Spinlock lock; pthread_t thread; Futex *futex; - Futex_Wait_Node *prev, *next; + Futex_Waitq *waitq; + Futex_Waiter *prev, *next; }; -struct Futex_Wait_Queue { - std::atomic_flag spinlock; - Futex_Wait_Node list; +struct Futex_Waitq { + _Spinlock lock; + Futex_Waiter list; - void lock() { - while (spinlock.test_and_set(std::memory_order_acquire)) { - ; // spin... - } - } - - void unlock() { - spinlock.clear(std::memory_order_release); + void init() { + auto head = &list; + head->prev = head->next = head; } }; // FIXME: This approach may scale badly in the future, // possible solution - hash map (leads to deadlocks now). -Futex_Wait_Queue g_waitq = { - .spinlock = ATOMIC_FLAG_INIT, +Futex_Waitq g_waitq = { + .lock = ATOMIC_FLAG_INIT, .list = { .prev = &g_waitq.list, .next = &g_waitq.list, }, }; -Futex_Wait_Queue *get_wait_queue(Futex *f) { +Futex_Waitq *get_waitq(Futex *f) { // Future hash map method... return &g_waitq; } void futex_signal(Futex *f) { - auto waitq = get_wait_queue(f); + auto waitq = get_waitq(f); - waitq->lock(); + waitq->lock.lock(); auto head = &waitq->list; for (auto waiter = head->next; waiter != head; waiter = waiter->next) { - if (waiter->futex == f) { - pthread_kill(waiter->thread, SIGCONT); - break; - } + if (waiter->futex != f) { + continue; + } + waitq->lock.unlock(); + pthread_kill(waiter->thread, SIGCONT); + return; } - waitq->unlock(); + waitq->lock.unlock(); } void futex_broadcast(Futex *f) { - auto waitq = get_wait_queue(f); + auto waitq = get_waitq(f); - waitq->lock(); + waitq->lock.lock(); auto head = &waitq->list; for (auto waiter = head->next; waiter != head; waiter = waiter->next) { - if (waiter->futex == f) { + if (waiter->futex != f) { + continue; + } + if (waiter->next == head) { + waitq->lock.unlock(); pthread_kill(waiter->thread, SIGCONT); - } + return; + } else { + pthread_kill(waiter->thread, SIGCONT); + } } - waitq->unlock(); + waitq->lock.unlock(); } void futex_wait(Futex *f, Footex val) { - auto waitq = get_wait_queue(f); - - waitq->lock(); - - auto head = &waitq->list; - Futex_Wait_Node waiter; + Futex_Waiter waiter; waiter.thread = pthread_self(); waiter.futex = f; - waiter.prev = head; - waiter.next = head->next; + + auto waitq = get_waitq(f); + while (waitq->lock.state.test_and_set(std::memory_order_acquire)) { + if (f->load(std::memory_order_relaxed) != val) { + return; + } + #if defined(GB_CPU_X86) + _mm_pause(); + #else + (void)0; // spin... + #endif + } + + waiter.waitq = waitq; + waiter.lock.init(); + waiter.lock.lock(); + + auto head = &waitq->list; + waiter.prev = head->prev; + waiter.next = head; + waiter.prev->next = &waiter; + waiter.next->prev = &waiter; waiter.prev->next = &waiter; waiter.next->prev = &waiter; @@ -928,12 +973,25 @@ void futex_wait(Futex *f, Footex val) { sigemptyset(&mask); sigaddset(&mask, SIGCONT); pthread_sigmask(SIG_BLOCK, &mask, &old_mask); - - if (*f == val) { - waitq->unlock(); - int sig; - sigwait(&mask, &sig); - waitq->lock(); + + if (f->load(std::memory_order_relaxed) == val) { + waiter.lock.unlock(); + waitq->lock.unlock(); + + int sig; + sigwait(&mask, &sig); + + waitq->lock.lock(); + waiter.lock.lock(); + + while (waitq != waiter.waitq) { + auto req = waiter.waitq; + waiter.lock.unlock(); + waitq->lock.unlock(); + waitq = req; + waitq->lock.lock(); + waiter.lock.lock(); + } } waiter.prev->next = waiter.next; @@ -941,7 +999,8 @@ void futex_wait(Futex *f, Footex val) { pthread_sigmask(SIG_SETMASK, &old_mask, NULL); - waitq->unlock(); + waiter.lock.unlock(); + waitq->lock.unlock(); } #endif -- cgit v1.2.3