From 60d0390ef8ceabb0567ee1ba968fdaf2024d34bf Mon Sep 17 00:00:00 2001 From: gingerBill Date: Sun, 1 Jan 2023 14:48:31 +0000 Subject: Unify compiler `Futex` interface --- src/threading.cpp | 43 +++++++++++++++++-------------------------- 1 file changed, 17 insertions(+), 26 deletions(-) (limited to 'src/threading.cpp') diff --git a/src/threading.cpp b/src/threading.cpp index 493e57c91..cb3150c2a 100644 --- a/src/threading.cpp +++ b/src/threading.cpp @@ -41,6 +41,11 @@ struct Thread { struct ThreadPool *pool; }; +typedef std::atomic Futex; +typedef volatile int32_t Footex; + +gb_internal void futex_wait(Futex *addr, Footex val); +gb_internal void futex_signal(Futex *addr); gb_internal void mutex_init (BlockingMutex *m); gb_internal void mutex_destroy (BlockingMutex *m); @@ -441,12 +446,9 @@ gb_internal void thread_set_name(Thread *t, char const *name) { #include #include -typedef std::atomic Futex; -typedef volatile int32_t Footex; - -gb_internal void tpool_wake_addr(Futex *addr) { +gb_internal void futex_signal(Futex *addr) { for (;;) { - int ret = syscall(SYS_futex, addr, FUTEX_WAKE, 1, NULL, NULL, 0); + int ret = syscall(SYS_futex, addr, FUTEX_WAKE | FUTEX_PRIVATE_FLAG, 1, NULL, NULL, 0); if (ret == -1) { perror("Futex wake"); GB_PANIC("Failed in futex wake!\n"); @@ -456,9 +458,9 @@ gb_internal void tpool_wake_addr(Futex *addr) { } } -gb_internal void tpool_wait_on_addr(Futex *addr, Footex val) { +gb_internal void futex_wait(Futex *addr, Footex val) { for (;;) { - int ret = syscall(SYS_futex, addr, FUTEX_WAIT, val, NULL, NULL, 0); + int ret = syscall(SYS_futex, addr, FUTEX_WAIT | FUTEX_PRIVATE_FLAG, val, NULL, NULL, 0); if (ret == -1) { if (errno != EAGAIN) { perror("Futex wait"); @@ -479,14 +481,11 @@ gb_internal void tpool_wait_on_addr(Futex *addr, Footex val) { #include #include -typedef std::atomic Futex; -typedef volatile int32_t Footex; - -gb_internal void tpool_wake_addr(Futex *addr) { +gb_internal void futex_signal(Futex *addr) { _umtx_op(addr, UMTX_OP_WAKE, 1, 0, 0); } -gb_internal void tpool_wait_on_addr(Futex *addr, Footex val) { +gb_internal void futex_wait(Futex *addr, Footex val) { for (;;) { int ret = _umtx_op(addr, UMTX_OP_WAIT_UINT, val, 0, NULL); if (ret == 0) { @@ -508,10 +507,7 @@ gb_internal void tpool_wait_on_addr(Futex *addr, Footex val) { #include -typedef std::atomic Futex; -typedef volatile int32_t Footex; - -gb_internal void tpool_wake_addr(Futex *addr) { +gb_internal void futex_signal(Futex *addr) { for (;;) { int ret = futex((volatile uint32_t *)addr, FUTEX_WAKE | FUTEX_PRIVATE_FLAG, 1, NULL, NULL); if (ret == -1) { @@ -527,7 +523,7 @@ gb_internal void tpool_wake_addr(Futex *addr) { } } -gb_internal void tpool_wait_on_addr(Futex *addr, Footex val) { +gb_internal void futex_wait(Futex *addr, Footex val) { for (;;) { int ret = futex((volatile uint32_t *)addr, FUTEX_WAIT | FUTEX_PRIVATE_FLAG, val, NULL, NULL); if (ret == -1) { @@ -547,16 +543,13 @@ gb_internal void tpool_wait_on_addr(Futex *addr, Footex val) { #elif defined(GB_SYSTEM_OSX) -typedef std::atomic Futex; -typedef volatile int64_t Footex; - #define UL_COMPARE_AND_WAIT 0x00000001 #define ULF_NO_ERRNO 0x01000000 extern "C" int __ulock_wait(uint32_t operation, void *addr, uint64_t value, uint32_t timeout); /* timeout is specified in microseconds */ extern "C" int __ulock_wake(uint32_t operation, void *addr, uint64_t wake_value); -gb_internal void tpool_wake_addr(Futex *addr) { +gb_internal void futex_signal(Futex *addr) { for (;;) { int ret = __ulock_wake(UL_COMPARE_AND_WAIT | ULF_NO_ERRNO, addr, 0); if (ret >= 0) { @@ -572,7 +565,7 @@ gb_internal void tpool_wake_addr(Futex *addr) { } } -gb_internal void tpool_wait_on_addr(Futex *addr, Footex val) { +gb_internal void futex_wait(Futex *addr, Footex val) { for (;;) { int ret = __ulock_wait(UL_COMPARE_AND_WAIT | ULF_NO_ERRNO, addr, val, 0); if (ret >= 0) { @@ -592,14 +585,12 @@ gb_internal void tpool_wait_on_addr(Futex *addr, Footex val) { } } #elif defined(GB_SYSTEM_WINDOWS) -typedef std::atomic Futex; -typedef volatile int64_t Footex; -gb_internal void tpool_wake_addr(Futex *addr) { +gb_internal void futex_signal(Futex *addr) { WakeByAddressSingle((void *)addr); } -gb_internal void tpool_wait_on_addr(Futex *addr, Footex val) { +gb_internal void futex_wait(Futex *addr, Footex val) { for (;;) { WaitOnAddress(addr, (void *)&val, sizeof(val), INFINITE); if (*addr != val) break; -- cgit v1.2.3 From 20d451396d68d749b6c7ce762bc14e44f219e299 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Sun, 1 Jan 2023 15:06:57 +0000 Subject: Begin work on futex-ifying the threading primitives --- src/threading.cpp | 172 +++++++++++++++++++++++++++++++++++++++++------------- 1 file changed, 133 insertions(+), 39 deletions(-) (limited to 'src/threading.cpp') diff --git a/src/threading.cpp b/src/threading.cpp index cb3150c2a..646c0e93b 100644 --- a/src/threading.cpp +++ b/src/threading.cpp @@ -41,11 +41,12 @@ struct Thread { struct ThreadPool *pool; }; -typedef std::atomic Futex; -typedef volatile int32_t Footex; +typedef std::atomic Futex; +typedef volatile i32 Footex; gb_internal void futex_wait(Futex *addr, Footex val); gb_internal void futex_signal(Futex *addr); +gb_internal void futex_broadcast(Futex *addr); gb_internal void mutex_init (BlockingMutex *m); gb_internal void mutex_destroy (BlockingMutex *m); @@ -117,6 +118,82 @@ struct MutexGuard { #define MUTEX_GUARD(m) MutexGuard GB_DEFER_3(_mutex_guard_){m} +struct RecursiveMutex { + Futex owner; + i32 recursion; +}; +gb_internal void mutex_init(RecursiveMutex *m) { + +} +gb_internal void mutex_destroy(RecursiveMutex *m) { + +} +gb_internal void mutex_lock(RecursiveMutex *m) { + Futex tid = cast(i32)thread_current_id(); + for (;;) { + i32 prev_owner = 0; + m->owner.compare_exchange_strong(prev_owner, tid, std::memory_order_acquire, std::memory_order_acquire); + if (prev_owner == 0 || prev_owner == tid) { + m->recursion++; + // inside the lock + return; + } + futex_wait(&m->owner, prev_owner); + } +} +gb_internal bool mutex_try_lock(RecursiveMutex *m) { + Futex tid = cast(i32)thread_current_id(); + i32 prev_owner = 0; + m->owner.compare_exchange_strong(prev_owner, tid, std::memory_order_acquire, std::memory_order_acquire); + if (prev_owner == 0 || prev_owner == tid) { + m->recursion++; + // inside the lock + return true; + } + return false; +} +gb_internal void mutex_unlock(RecursiveMutex *m) { + m->recursion--; + if (m->recursion != 0) { + return; + } + m->owner.exchange(0, std::memory_order_release); + futex_signal(&m->owner); + // outside the lock +} + +struct Semaphore { + Futex count; +}; + +gb_internal void semaphore_init(Semaphore *s) { + +} +gb_internal void semaphore_destroy(Semaphore *s) { + +} +gb_internal void semaphore_post(Semaphore *s, i32 count) { + s->count.fetch_add(count, std::memory_order_release); + if (s->count == 1) { + futex_signal(&s->count); + } else { + futex_broadcast(&s->count); + } +} +gb_internal void semaphore_wait(Semaphore *s) { + for (;;) { + i32 original_count = s->count.load(std::memory_order_relaxed); + while (original_count == 0) { + futex_wait(&s->count, original_count); + original_count = s->count; + } + + if (!s->count.compare_exchange_strong(original_count, original_count-1, std::memory_order_acquire, std::memory_order_acquire)) { + return; + } + } +} + #if defined(GB_SYSTEM_WINDOWS) struct BlockingMutex { SRWLOCK srwlock; @@ -135,42 +212,6 @@ struct MutexGuard { ReleaseSRWLockExclusive(&m->srwlock); } - struct RecursiveMutex { - CRITICAL_SECTION win32_critical_section; - }; - gb_internal void mutex_init(RecursiveMutex *m) { - InitializeCriticalSection(&m->win32_critical_section); - } - gb_internal void mutex_destroy(RecursiveMutex *m) { - DeleteCriticalSection(&m->win32_critical_section); - } - gb_internal void mutex_lock(RecursiveMutex *m) { - EnterCriticalSection(&m->win32_critical_section); - } - gb_internal bool mutex_try_lock(RecursiveMutex *m) { - return TryEnterCriticalSection(&m->win32_critical_section) != 0; - } - gb_internal void mutex_unlock(RecursiveMutex *m) { - LeaveCriticalSection(&m->win32_critical_section); - } - - struct Semaphore { - void *win32_handle; - }; - - gb_internal void semaphore_init(Semaphore *s) { - s->win32_handle = CreateSemaphoreA(NULL, 0, I32_MAX, NULL); - } - gb_internal void semaphore_destroy(Semaphore *s) { - CloseHandle(s->win32_handle); - } - gb_internal void semaphore_post(Semaphore *s, i32 count) { - ReleaseSemaphore(s->win32_handle, count, NULL); - } - gb_internal void semaphore_wait(Semaphore *s) { - WaitForSingleObjectEx(s->win32_handle, INFINITE, FALSE); - } - struct Condition { CONDITION_VARIABLE cond; }; @@ -458,6 +499,18 @@ gb_internal void futex_signal(Futex *addr) { } } +gb_internal void futex_broadcast(Futex *addr) { + for (;;) { + int ret = syscall(SYS_futex, addr, FUTEX_WAKE | FUTEX_PRIVATE_FLAG, INT32_MAX, NULL, NULL, 0); + if (ret == -1) { + perror("Futex wake"); + GB_PANIC("Failed in futex wake!\n"); + } else if (ret > 0) { + return; + } + } +} + gb_internal void futex_wait(Futex *addr, Footex val) { for (;;) { int ret = syscall(SYS_futex, addr, FUTEX_WAIT | FUTEX_PRIVATE_FLAG, val, NULL, NULL, 0); @@ -485,6 +538,10 @@ gb_internal void futex_signal(Futex *addr) { _umtx_op(addr, UMTX_OP_WAKE, 1, 0, 0); } +gb_internal void futex_broadcast(Futex *addr) { + _umtx_op(addr, UMTX_OP_WAKE, INT32_MAX, 0, 0); +} + gb_internal void futex_wait(Futex *addr, Footex val) { for (;;) { int ret = _umtx_op(addr, UMTX_OP_WAIT_UINT, val, 0, NULL); @@ -523,6 +580,23 @@ gb_internal void futex_signal(Futex *addr) { } } + +gb_internal void futex_broadcast(Futex *addr) { + for (;;) { + int ret = futex((volatile uint32_t *)addr, FUTEX_WAKE | FUTEX_PRIVATE_FLAG, INT32_MAX, NULL, NULL); + if (ret == -1) { + if (errno == ETIMEDOUT || errno == EINTR) { + continue; + } + + perror("Futex wake"); + GB_PANIC("futex wake fail"); + } else if (ret == 1) { + return; + } + } +} + gb_internal void futex_wait(Futex *addr, Footex val) { for (;;) { int ret = futex((volatile uint32_t *)addr, FUTEX_WAIT | FUTEX_PRIVATE_FLAG, val, NULL, NULL); @@ -565,9 +639,25 @@ gb_internal void futex_signal(Futex *addr) { } } +gb_internal void futex_broadcast(Futex *addr) { + for (;;) { + int ret = __ulock_wake(UL_COMPARE_AND_WAIT | ULF_NO_ERRNO, addr, 0); + if (ret >= 0) { + return; + } + if (ret == EINTR || ret == EFAULT) { + continue; + } + if (ret == ENOENT) { + return; + } + GB_PANIC("Failed in futex wake!\n"); + } +} + gb_internal void futex_wait(Futex *addr, Footex val) { for (;;) { - int ret = __ulock_wait(UL_COMPARE_AND_WAIT | ULF_NO_ERRNO, addr, val, 0); + int ret = __ulock_wait(UL_COMPARE_AND_WAIT | ULF_NO_ERRNO | ULF_WAKE_ALL, addr, val, 0); if (ret >= 0) { if (*addr != val) { return; @@ -590,6 +680,10 @@ gb_internal void futex_signal(Futex *addr) { WakeByAddressSingle((void *)addr); } +gb_internal void futex_broadcast(Futex *addr) { + WakeByAddressAll((void *)addr); +} + gb_internal void futex_wait(Futex *addr, Footex val) { for (;;) { WaitOnAddress(addr, (void *)&val, sizeof(val), INFINITE); -- cgit v1.2.3 From 74e6d9144e9a0afd9c29b0edec8c6ed2960efde4 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Sun, 1 Jan 2023 16:15:35 +0000 Subject: Get around the std::atomic issue --- src/threading.cpp | 160 ++++++++++++++++++++++++++++++------------------------ 1 file changed, 88 insertions(+), 72 deletions(-) (limited to 'src/threading.cpp') diff --git a/src/threading.cpp b/src/threading.cpp index 646c0e93b..7dd1247e7 100644 --- a/src/threading.cpp +++ b/src/threading.cpp @@ -234,95 +234,111 @@ gb_internal void semaphore_wait(Semaphore *s) { } #else + enum Internal_Mutex_State : i32 { + Internal_Mutex_State_Unlocked = 0, + Internal_Mutex_State_Locked = 1, + Internal_Mutex_State_Waiting = 2, + }; + struct BlockingMutex { - pthread_mutex_t pthread_mutex; + i32 state_; + + Futex &state() { + return *(Futex *)&this->state_; + } + Futex const &state() const { + return *(Futex const *)&this->state_; + } }; - gb_internal void mutex_init(BlockingMutex *m) { - pthread_mutex_init(&m->pthread_mutex, nullptr); - } - gb_internal void mutex_destroy(BlockingMutex *m) { - pthread_mutex_destroy(&m->pthread_mutex); + + gb_internal void mutex_init(BlockingMutex *m) {}; + gb_internal void mutex_destroy(BlockingMutex *m) {}; + + gb_no_inline gb_internal void mutex_lock_slow(BlockingMutex *m, i32 curr_state) { + i32 new_state = curr_state; + for (i32 spin = 0; spin < 100; spin++) { + i32 state = Internal_Mutex_State_Unlocked; + bool ok = m->state().compare_exchange_weak(state, new_state, std::memory_order_acquire, std::memory_order_consume); + if (ok) { + return; + } + if (state == Internal_Mutex_State_Waiting) { + break; + } + for (i32 i = gb_min(spin+1, 32); i > 0; i--) { + yield_thread(); + } + } + + // Set just in case 100 iterations did not do it + new_state = Internal_Mutex_State_Waiting; + + for (;;) { + if (m->state().exchange(Internal_Mutex_State_Waiting, std::memory_order_acquire) == Internal_Mutex_State_Unlocked) { + return; + } + futex_wait(&m->state(), new_state); + yield_thread(); + } } + gb_internal void mutex_lock(BlockingMutex *m) { - pthread_mutex_lock(&m->pthread_mutex); + i32 v = m->state().exchange(Internal_Mutex_State_Locked, std::memory_order_acquire); + if (v != Internal_Mutex_State_Unlocked) { + mutex_lock_slow(m, v); + } } gb_internal bool mutex_try_lock(BlockingMutex *m) { - return pthread_mutex_trylock(&m->pthread_mutex) == 0; + i32 v = m->state().exchange(Internal_Mutex_State_Locked, std::memory_order_acquire); + return v == Internal_Mutex_State_Unlocked; } - gb_internal void mutex_unlock(BlockingMutex *m) { - pthread_mutex_unlock(&m->pthread_mutex); + + gb_no_inline gb_internal void mutex_unlock_slow(BlockingMutex *m) { + futex_signal(&m->state()); } - struct RecursiveMutex { - pthread_mutex_t pthread_mutex; - pthread_mutexattr_t pthread_mutexattr; - }; - gb_internal void mutex_init(RecursiveMutex *m) { - pthread_mutexattr_init(&m->pthread_mutexattr); - pthread_mutexattr_settype(&m->pthread_mutexattr, PTHREAD_MUTEX_RECURSIVE); - pthread_mutex_init(&m->pthread_mutex, &m->pthread_mutexattr); - } - gb_internal void mutex_destroy(RecursiveMutex *m) { - pthread_mutex_destroy(&m->pthread_mutex); - } - gb_internal void mutex_lock(RecursiveMutex *m) { - pthread_mutex_lock(&m->pthread_mutex); - } - gb_internal bool mutex_try_lock(RecursiveMutex *m) { - return pthread_mutex_trylock(&m->pthread_mutex) == 0; - } - gb_internal void mutex_unlock(RecursiveMutex *m) { - pthread_mutex_unlock(&m->pthread_mutex); - } - - #if defined(GB_SYSTEM_OSX) - struct Semaphore { - semaphore_t osx_handle; - }; - - gb_internal void semaphore_init (Semaphore *s) { semaphore_create(mach_task_self(), &s->osx_handle, SYNC_POLICY_FIFO, 0); } - gb_internal void semaphore_destroy(Semaphore *s) { semaphore_destroy(mach_task_self(), s->osx_handle); } - gb_internal void semaphore_post (Semaphore *s, i32 count) { while (count --> 0) semaphore_signal(s->osx_handle); } - gb_internal void semaphore_wait (Semaphore *s) { semaphore_wait(s->osx_handle); } - #elif defined(GB_SYSTEM_UNIX) - struct Semaphore { - sem_t unix_handle; - }; - - gb_internal void semaphore_init (Semaphore *s) { sem_init(&s->unix_handle, 0, 0); } - gb_internal void semaphore_destroy(Semaphore *s) { sem_destroy(&s->unix_handle); } - gb_internal void semaphore_post (Semaphore *s, i32 count) { while (count --> 0) sem_post(&s->unix_handle); } - void semaphore_wait (Semaphore *s) { int i; do { i = sem_wait(&s->unix_handle); } while (i == -1 && errno == EINTR); } - #else - #error Implement Semaphore for this platform - #endif - + gb_internal void mutex_unlock(BlockingMutex *m) { + i32 v = m->state().exchange(Internal_Mutex_State_Unlocked, std::memory_order_release); + switch (v) { + case Internal_Mutex_State_Unlocked: + GB_PANIC("Unreachable"); + break; + case Internal_Mutex_State_Locked: + // Okay + break; + case Internal_Mutex_State_Waiting: + mutex_unlock_slow(m); + break; + } + } struct Condition { - pthread_cond_t pthread_cond; + i32 state_; + + Futex &state() { + return *(Futex *)&this->state_; + } + Futex const &state() const { + return *(Futex const *)&this->state_; + } }; - - gb_internal void condition_init(Condition *c) { - pthread_cond_init(&c->pthread_cond, NULL); - } - gb_internal void condition_destroy(Condition *c) { - pthread_cond_destroy(&c->pthread_cond); - } + + gb_internal void condition_init(Condition *c) {} + gb_internal void condition_destroy(Condition *c) {} + gb_internal void condition_broadcast(Condition *c) { - pthread_cond_broadcast(&c->pthread_cond); + c->state().fetch_add(1, std::memory_order_release); + futex_broadcast(&c->state()); } gb_internal void condition_signal(Condition *c) { - pthread_cond_signal(&c->pthread_cond); + c->state().fetch_add(1, std::memory_order_release); + futex_signal(&c->state()); } gb_internal void condition_wait(Condition *c, BlockingMutex *m) { - pthread_cond_wait(&c->pthread_cond, &m->pthread_mutex); - } - gb_internal void condition_wait_with_timeout(Condition *c, BlockingMutex *m, u32 timeout_in_ms) { - struct timespec abstime = {}; - abstime.tv_sec = timeout_in_ms/1000; - abstime.tv_nsec = cast(long)(timeout_in_ms%1000)*1e6; - pthread_cond_timedwait(&c->pthread_cond, &m->pthread_mutex, &abstime); - + i32 state = c->state().load(std::memory_order_relaxed); + mutex_unlock(m); + futex_wait(&c->state(), state); + mutex_lock(m); } #endif -- cgit v1.2.3 From 5c519f0e8dada6b15166a257d22a07f2316a394f Mon Sep 17 00:00:00 2001 From: gingerBill Date: Sun, 1 Jan 2023 16:19:21 +0000 Subject: Remove the synchronization primitive init/destroy calls --- src/build_settings.cpp | 1 - src/checker.cpp | 36 ------------------------------------ src/common_memory.cpp | 2 -- src/entity.cpp | 1 - src/error.cpp | 4 ---- src/llvm_backend_general.cpp | 1 - src/main.cpp | 5 ----- src/parser.cpp | 11 ----------- src/queue.cpp | 2 -- src/string.cpp | 5 ----- src/thread_pool.cpp | 5 ----- src/threading.cpp | 35 +---------------------------------- src/types.cpp | 4 ---- 13 files changed, 1 insertion(+), 111 deletions(-) (limited to 'src/threading.cpp') diff --git a/src/build_settings.cpp b/src/build_settings.cpp index 080e9dddc..97b512b81 100644 --- a/src/build_settings.cpp +++ b/src/build_settings.cpp @@ -1363,7 +1363,6 @@ gb_internal bool init_build_paths(String init_filename) { array_init(&bc->build_paths, permanent_allocator(), BuildPathCOUNT); string_set_init(&bc->target_features_set, heap_allocator(), 1024); - mutex_init(&bc->target_features_mutex); // [BuildPathMainPackage] Turn given init path into a `Path`, which includes normalizing it into a full path. bc->build_paths[BuildPath_Main_Package] = path_from_string(ha, init_filename); diff --git a/src/checker.cpp b/src/checker.cpp index b78da2827..7141b0698 100644 --- a/src/checker.cpp +++ b/src/checker.cpp @@ -184,7 +184,6 @@ gb_internal void init_decl_info(DeclInfo *d, Scope *scope, DeclInfo *parent) { ptr_set_init(&d->deps, heap_allocator()); ptr_set_init(&d->type_info_deps, heap_allocator()); array_init (&d->labels, heap_allocator()); - mutex_init(&d->proc_checked_mutex); } gb_internal DeclInfo *make_decl_info(Scope *scope, DeclInfo *parent) { @@ -225,7 +224,6 @@ gb_internal Scope *create_scope(CheckerInfo *info, Scope *parent, isize init_ele s->parent = parent; string_map_init(&s->elements, heap_allocator(), init_elements_capacity); ptr_set_init(&s->imported, heap_allocator(), 0); - mutex_init(&s->mutex); if (parent != nullptr && parent != builtin_pkg->scope) { Scope *prev_head_child = parent->head_child.exchange(s, std::memory_order_acq_rel); @@ -306,7 +304,6 @@ gb_internal void destroy_scope(Scope *scope) { string_map_destroy(&scope->elements); ptr_set_destroy(&scope->imported); - mutex_destroy(&scope->mutex); // NOTE(bill): No need to free scope as it "should" be allocated in an arena (except for the global scope) } @@ -1134,24 +1131,9 @@ gb_internal void init_checker_info(CheckerInfo *i) { TIME_SECTION("checker info: mutexes"); - mutex_init(&i->gen_procs_mutex); - mutex_init(&i->gen_types_mutex); - mutex_init(&i->lazy_mutex); - mutex_init(&i->builtin_mutex); - mutex_init(&i->global_untyped_mutex); - mutex_init(&i->type_info_mutex); - mutex_init(&i->deps_mutex); - mutex_init(&i->type_and_value_mutex); - mutex_init(&i->identifier_uses_mutex); - mutex_init(&i->foreign_mutex); - - semaphore_init(&i->collect_semaphore); - mpmc_init(&i->intrinsics_entry_point_usage, a, 1<<10); // just waste some memory here, even if it probably never used - mutex_init(&i->objc_types_mutex); map_init(&i->objc_msgSend_types, a); - mutex_init(&i->load_file_mutex); string_map_init(&i->load_file_cache, a); } @@ -1175,20 +1157,7 @@ gb_internal void destroy_checker_info(CheckerInfo *i) { mpmc_destroy(&i->required_global_variable_queue); mpmc_destroy(&i->required_foreign_imports_through_force_queue); - mutex_destroy(&i->gen_procs_mutex); - mutex_destroy(&i->gen_types_mutex); - mutex_destroy(&i->lazy_mutex); - mutex_destroy(&i->builtin_mutex); - mutex_destroy(&i->global_untyped_mutex); - mutex_destroy(&i->type_info_mutex); - mutex_destroy(&i->deps_mutex); - mutex_destroy(&i->type_and_value_mutex); - mutex_destroy(&i->identifier_uses_mutex); - mutex_destroy(&i->foreign_mutex); - - mutex_destroy(&i->objc_types_mutex); map_destroy(&i->objc_msgSend_types); - mutex_init(&i->load_file_mutex); string_map_destroy(&i->load_file_cache); } @@ -1201,11 +1170,9 @@ gb_internal CheckerContext make_checker_context(Checker *c) { ctx.type_path = new_checker_type_path(); ctx.type_level = 0; - mutex_init(&ctx.mutex); return ctx; } gb_internal void destroy_checker_context(CheckerContext *ctx) { - mutex_destroy(&ctx->mutex); destroy_checker_type_path(ctx->type_path); } @@ -1264,7 +1231,6 @@ gb_internal void init_checker(Checker *c) { // NOTE(bill): 1 Mi elements should be enough on average mpmc_init(&c->procs_to_check_queue, heap_allocator(), 1<<20); - semaphore_init(&c->procs_to_check_semaphore); mpmc_init(&c->global_untyped_queue, a, 1<<20); @@ -1277,8 +1243,6 @@ gb_internal void destroy_checker(Checker *c) { destroy_checker_context(&c->builtin_ctx); mpmc_destroy(&c->procs_to_check_queue); - semaphore_destroy(&c->procs_to_check_semaphore); - mpmc_destroy(&c->global_untyped_queue); } diff --git a/src/common_memory.cpp b/src/common_memory.cpp index c8a62756a..2022554cf 100644 --- a/src/common_memory.cpp +++ b/src/common_memory.cpp @@ -42,8 +42,6 @@ gb_global BlockingMutex global_memory_allocator_mutex; gb_internal void platform_virtual_memory_init(void); gb_internal void virtual_memory_init(void) { - mutex_init(&global_memory_block_mutex); - mutex_init(&global_memory_allocator_mutex); platform_virtual_memory_init(); } diff --git a/src/entity.cpp b/src/entity.cpp index 0605a293a..f82a2fb05 100644 --- a/src/entity.cpp +++ b/src/entity.cpp @@ -154,7 +154,6 @@ struct TypeNameObjCMetadata { gb_internal TypeNameObjCMetadata *create_type_name_obj_c_metadata() { TypeNameObjCMetadata *md = gb_alloc_item(permanent_allocator(), TypeNameObjCMetadata); md->mutex = gb_alloc_item(permanent_allocator(), BlockingMutex); - mutex_init(md->mutex); array_init(&md->type_entries, heap_allocator()); array_init(&md->value_entries, heap_allocator()); return md; diff --git a/src/error.cpp b/src/error.cpp index 085e1a8dd..a0bb4ad5b 100644 --- a/src/error.cpp +++ b/src/error.cpp @@ -22,10 +22,6 @@ gb_internal bool any_errors(void) { } gb_internal void init_global_error_collector(void) { - mutex_init(&global_error_collector.mutex); - mutex_init(&global_error_collector.block_mutex); - mutex_init(&global_error_collector.error_out_mutex); - mutex_init(&global_error_collector.string_mutex); array_init(&global_error_collector.errors, heap_allocator()); array_init(&global_error_collector.error_buffer, heap_allocator()); array_init(&global_file_path_strings, heap_allocator(), 1, 4096); diff --git a/src/llvm_backend_general.cpp b/src/llvm_backend_general.cpp index e5aa95f10..0508c6171 100644 --- a/src/llvm_backend_general.cpp +++ b/src/llvm_backend_general.cpp @@ -132,7 +132,6 @@ gb_internal bool lb_init_generator(lbGenerator *gen, Checker *c) { map_init(&gen->anonymous_proc_lits, heap_allocator(), 1024); - mutex_init(&gen->foreign_mutex); array_init(&gen->foreign_libraries, heap_allocator(), 0, 1024); ptr_set_init(&gen->foreign_libraries_set, heap_allocator(), 1024); diff --git a/src/main.cpp b/src/main.cpp index 6d910c7bf..184ab471e 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -2498,15 +2498,10 @@ int main(int arg_count, char const **arg_ptr) { MAIN_TIME_SECTION("initialization"); virtual_memory_init(); - mutex_init(&fullpath_mutex); - mutex_init(&hash_exact_value_mutex); - mutex_init(&global_type_name_objc_metadata_mutex); - init_string_buffer_memory(); init_string_interner(); init_global_error_collector(); init_keyword_hash_table(); - init_type_mutex(); if (!check_env()) { return 1; diff --git a/src/parser.cpp b/src/parser.cpp index e07f26004..344dcb20d 100644 --- a/src/parser.cpp +++ b/src/parser.cpp @@ -4858,10 +4858,6 @@ gb_internal bool init_parser(Parser *p) { GB_ASSERT(p != nullptr); string_set_init(&p->imported_files, heap_allocator()); array_init(&p->packages, heap_allocator()); - mutex_init(&p->imported_files_mutex); - mutex_init(&p->file_decl_mutex); - mutex_init(&p->packages_mutex); - mutex_init(&p->file_error_mutex); return true; } @@ -4878,10 +4874,6 @@ gb_internal void destroy_parser(Parser *p) { } array_free(&p->packages); string_set_destroy(&p->imported_files); - mutex_destroy(&p->imported_files_mutex); - mutex_destroy(&p->file_decl_mutex); - mutex_destroy(&p->packages_mutex); - mutex_destroy(&p->file_error_mutex); } @@ -4978,9 +4970,6 @@ gb_internal AstPackage *try_add_import_path(Parser *p, String const &path, Strin pkg->fullpath = path; array_init(&pkg->files, heap_allocator()); pkg->foreign_files.allocator = heap_allocator(); - mutex_init(&pkg->files_mutex); - mutex_init(&pkg->foreign_files_mutex); - // NOTE(bill): Single file initial package if (kind == Package_Init && string_ends_with(path, FILE_EXT)) { diff --git a/src/queue.cpp b/src/queue.cpp index 4de5ac5e5..8f279bb21 100644 --- a/src/queue.cpp +++ b/src/queue.cpp @@ -52,7 +52,6 @@ gb_internal void mpmc_init(MPMCQueue *q, gbAllocator a, isize size_i) { size = next_pow2(size); GB_ASSERT(gb_is_power_of_two(size)); - mutex_init(&q->mutex); q->mask = size-1; q->allocator = a; q->nodes = gb_alloc_array(a, T, size); @@ -65,7 +64,6 @@ gb_internal void mpmc_init(MPMCQueue *q, gbAllocator a, isize size_i) { template gb_internal void mpmc_destroy(MPMCQueue *q) { - mutex_destroy(&q->mutex); gb_free(q->allocator, q->nodes); gb_free(q->allocator, q->indices); } diff --git a/src/string.cpp b/src/string.cpp index 8cce0f1ef..a2254d100 100644 --- a/src/string.cpp +++ b/src/string.cpp @@ -1,10 +1,5 @@ gb_global BlockingMutex string_buffer_mutex = {}; -gb_internal void init_string_buffer_memory(void) { - mutex_init(&string_buffer_mutex); -} - - // NOTE(bill): Used for UTF-8 strings struct String { u8 * text; diff --git a/src/thread_pool.cpp b/src/thread_pool.cpp index 57ed5e3c5..522b96d09 100644 --- a/src/thread_pool.cpp +++ b/src/thread_pool.cpp @@ -23,9 +23,6 @@ struct ThreadPool { }; gb_internal void thread_pool_init(ThreadPool *pool, gbAllocator const &a, isize thread_count, char const *worker_name) { - mutex_init(&pool->task_lock); - condition_init(&pool->tasks_available); - pool->allocator = a; slice_init(&pool->threads, a, thread_count + 1); @@ -54,8 +51,6 @@ gb_internal void thread_pool_destroy(ThreadPool *pool) { } gb_free(pool->allocator, pool->threads.data); - mutex_destroy(&pool->task_lock); - condition_destroy(&pool->tasks_available); } void thread_pool_queue_push(Thread *thread, WorkerTask task) { diff --git a/src/threading.cpp b/src/threading.cpp index 7dd1247e7..fb71a2c29 100644 --- a/src/threading.cpp +++ b/src/threading.cpp @@ -48,30 +48,22 @@ gb_internal void futex_wait(Futex *addr, Footex val); gb_internal void futex_signal(Futex *addr); gb_internal void futex_broadcast(Futex *addr); -gb_internal void mutex_init (BlockingMutex *m); -gb_internal void mutex_destroy (BlockingMutex *m); gb_internal void mutex_lock (BlockingMutex *m); gb_internal bool mutex_try_lock(BlockingMutex *m); gb_internal void mutex_unlock (BlockingMutex *m); -gb_internal void mutex_init (RecursiveMutex *m); -gb_internal void mutex_destroy (RecursiveMutex *m); + gb_internal void mutex_lock (RecursiveMutex *m); gb_internal bool mutex_try_lock(RecursiveMutex *m); gb_internal void mutex_unlock (RecursiveMutex *m); -gb_internal void semaphore_init (Semaphore *s); -gb_internal void semaphore_destroy(Semaphore *s); gb_internal void semaphore_post (Semaphore *s, i32 count); gb_internal void semaphore_wait (Semaphore *s); gb_internal void semaphore_release(Semaphore *s) { semaphore_post(s, 1); } -gb_internal void condition_init(Condition *c); -gb_internal void condition_destroy(Condition *c); gb_internal void condition_broadcast(Condition *c); gb_internal void condition_signal(Condition *c); gb_internal void condition_wait(Condition *c, BlockingMutex *m); -gb_internal void condition_wait_with_timeout(Condition *c, BlockingMutex *m, u32 timeout_in_ms); gb_internal u32 thread_current_id(void); @@ -122,12 +114,7 @@ struct RecursiveMutex { Futex owner; i32 recursion; }; -gb_internal void mutex_init(RecursiveMutex *m) { - -} -gb_internal void mutex_destroy(RecursiveMutex *m) { -} gb_internal void mutex_lock(RecursiveMutex *m) { Futex tid = cast(i32)thread_current_id(); for (;;) { @@ -166,12 +153,6 @@ struct Semaphore { Futex count; }; -gb_internal void semaphore_init(Semaphore *s) { - -} -gb_internal void semaphore_destroy(Semaphore *s) { - -} gb_internal void semaphore_post(Semaphore *s, i32 count) { s->count.fetch_add(count, std::memory_order_release); if (s->count == 1) { @@ -198,10 +179,6 @@ gb_internal void semaphore_wait(Semaphore *s) { struct BlockingMutex { SRWLOCK srwlock; }; - gb_internal void mutex_init(BlockingMutex *m) { - } - gb_internal void mutex_destroy(BlockingMutex *m) { - } gb_internal void mutex_lock(BlockingMutex *m) { AcquireSRWLockExclusive(&m->srwlock); } @@ -229,10 +206,6 @@ gb_internal void semaphore_wait(Semaphore *s) { gb_internal void condition_wait(Condition *c, BlockingMutex *m) { SleepConditionVariableSRW(&c->cond, &m->srwlock, INFINITE, 0); } - gb_internal void condition_wait_with_timeout(Condition *c, BlockingMutex *m, u32 timeout_in_ms) { - SleepConditionVariableSRW(&c->cond, &m->srwlock, timeout_in_ms, 0); - } - #else enum Internal_Mutex_State : i32 { Internal_Mutex_State_Unlocked = 0, @@ -251,9 +224,6 @@ gb_internal void semaphore_wait(Semaphore *s) { } }; - gb_internal void mutex_init(BlockingMutex *m) {}; - gb_internal void mutex_destroy(BlockingMutex *m) {}; - gb_no_inline gb_internal void mutex_lock_slow(BlockingMutex *m, i32 curr_state) { i32 new_state = curr_state; for (i32 spin = 0; spin < 100; spin++) { @@ -323,9 +293,6 @@ gb_internal void semaphore_wait(Semaphore *s) { } }; - gb_internal void condition_init(Condition *c) {} - gb_internal void condition_destroy(Condition *c) {} - gb_internal void condition_broadcast(Condition *c) { c->state().fetch_add(1, std::memory_order_release); futex_broadcast(&c->state()); diff --git a/src/types.cpp b/src/types.cpp index 5bddfc79e..afe0b7d5d 100644 --- a/src/types.cpp +++ b/src/types.cpp @@ -808,10 +808,6 @@ gb_internal void type_path_pop(TypePath *tp) { #define FAILURE_SIZE 0 #define FAILURE_ALIGNMENT 0 -gb_internal void init_type_mutex(void) { - mutex_init(&g_type_mutex); -} - gb_internal bool type_ptr_set_update(PtrSet *s, Type *t) { if (ptr_set_exists(s, t)) { return true; -- cgit v1.2.3 From 3c90a059571cb879a468a00c0ca26c9a35090c38 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Mon, 2 Jan 2023 00:26:17 +0000 Subject: Replace condition+mutex with futex --- src/checker.cpp | 3 ++- src/thread_pool.cpp | 72 +++++++++++++++++++++++++---------------------------- src/threading.cpp | 4 ++- 3 files changed, 39 insertions(+), 40 deletions(-) (limited to 'src/threading.cpp') diff --git a/src/checker.cpp b/src/checker.cpp index 7141b0698..03ff901eb 100644 --- a/src/checker.cpp +++ b/src/checker.cpp @@ -1935,7 +1935,7 @@ gb_internal void add_type_info_type_internal(CheckerContext *c, Type *t) { -gb_global bool global_procedure_body_in_worker_queue = false; +gb_global std::atomic global_procedure_body_in_worker_queue = false; gb_internal void check_procedure_later(CheckerContext *c, ProcInfo *info) { GB_ASSERT(info != nullptr); @@ -5264,6 +5264,7 @@ gb_internal WORKER_TASK_PROC(thread_proc_body) { gb_internal void check_procedure_bodies(Checker *c) { GB_ASSERT(c != nullptr); + u32 thread_count = cast(u32)gb_max(build_context.thread_count, 1); u32 worker_count = thread_count-1; // NOTE(bill): The main thread will also be used for work if (!build_context.threaded_checker) { diff --git a/src/thread_pool.cpp b/src/thread_pool.cpp index 522b96d09..768a92645 100644 --- a/src/thread_pool.cpp +++ b/src/thread_pool.cpp @@ -16,8 +16,7 @@ struct ThreadPool { Slice threads; std::atomic running; - BlockingMutex task_lock; - Condition tasks_available; + Futex tasks_available; Futex tasks_left; }; @@ -43,27 +42,25 @@ gb_internal void thread_pool_destroy(ThreadPool *pool) { for_array_off(i, 1, pool->threads) { Thread *t = &pool->threads[i]; - condition_broadcast(&pool->tasks_available); + pool->tasks_available.fetch_add(1, std::memory_order_release); + futex_broadcast(&pool->tasks_available); thread_join_and_destroy(t); } - for_array(i, pool->threads) { - free(pool->threads[i].queue); - } gb_free(pool->allocator, pool->threads.data); } void thread_pool_queue_push(Thread *thread, WorkerTask task) { - uint64_t capture; - uint64_t new_capture; + u64 capture; + u64 new_capture; do { capture = thread->head_and_tail.load(); - uint64_t mask = thread->capacity - 1; - uint64_t head = (capture >> 32) & mask; - uint64_t tail = ((uint32_t)capture) & mask; + u64 mask = thread->capacity - 1; + u64 head = (capture >> 32) & mask; + u64 tail = ((u32)capture) & mask; - uint64_t new_head = (head + 1) & mask; + u64 new_head = (head + 1) & mask; if (new_head == tail) { GB_PANIC("Thread Queue Full!\n"); } @@ -73,21 +70,22 @@ void thread_pool_queue_push(Thread *thread, WorkerTask task) { new_capture = (new_head << 32) | tail; } while (!thread->head_and_tail.compare_exchange_weak(capture, new_capture)); - thread->pool->tasks_left.fetch_add(1); - condition_broadcast(&thread->pool->tasks_available); + thread->pool->tasks_left.fetch_add(1, std::memory_order_release); + thread->pool->tasks_available.fetch_add(1, std::memory_order_release); + futex_broadcast(&thread->pool->tasks_available); } bool thread_pool_queue_pop(Thread *thread, WorkerTask *task) { - uint64_t capture; - uint64_t new_capture; + u64 capture; + u64 new_capture; do { capture = thread->head_and_tail.load(); - uint64_t mask = thread->capacity - 1; - uint64_t head = (capture >> 32) & mask; - uint64_t tail = ((uint32_t)capture) & mask; + u64 mask = thread->capacity - 1; + u64 head = (capture >> 32) & mask; + u64 tail = ((u32)capture) & mask; - uint64_t new_tail = (tail + 1) & mask; + u64 new_tail = (tail + 1) & mask; if (tail == head) { return false; } @@ -113,12 +111,11 @@ gb_internal bool thread_pool_add_task(ThreadPool *pool, WorkerTaskProc *proc, vo gb_internal void thread_pool_wait(ThreadPool *pool) { WorkerTask task; - while (pool->tasks_left) { - + while (pool->tasks_left.load()) { // if we've got tasks on our queue, run them while (thread_pool_queue_pop(current_thread, &task)) { task.do_work(task.data); - pool->tasks_left.fetch_sub(1); + pool->tasks_left.fetch_sub(1, std::memory_order_release); } @@ -127,8 +124,8 @@ gb_internal void thread_pool_wait(ThreadPool *pool) { // if rem_tasks has changed since we checked last, otherwise the program // will permanently sleep Footex rem_tasks = pool->tasks_left.load(); - if (!rem_tasks) { - break; + if (rem_tasks == 0) { + return; } futex_wait(&pool->tasks_left, rem_tasks); @@ -147,37 +144,37 @@ work_start: } // If we've got tasks to process, work through them - size_t finished_tasks = 0; + usize finished_tasks = 0; while (thread_pool_queue_pop(current_thread, &task)) { task.do_work(task.data); - pool->tasks_left.fetch_sub(1); + pool->tasks_left.fetch_sub(1, std::memory_order_release); finished_tasks += 1; } - if (finished_tasks > 0 && !pool->tasks_left) { + if (finished_tasks > 0 && pool->tasks_left.load() == 0) { futex_signal(&pool->tasks_left); } // If there's still work somewhere and we don't have it, steal it - if (pool->tasks_left) { - isize idx = current_thread->idx; + if (pool->tasks_left.load()) { + usize idx = cast(usize)current_thread->idx; for_array(i, pool->threads) { - if (!pool->tasks_left) { + if (pool->tasks_left.load() == 0) { break; } - idx = (idx + 1) % pool->threads.count; - Thread *thread = &pool->threads[idx]; + idx = (idx + 1) % cast(usize)pool->threads.count; + Thread *thread = &pool->threads.data[idx]; WorkerTask task; if (!thread_pool_queue_pop(thread, &task)) { continue; } task.do_work(task.data); - pool->tasks_left.fetch_sub(1); + pool->tasks_left.fetch_sub(1, std::memory_order_release); - if (!pool->tasks_left) { + if (pool->tasks_left.load() == 0) { futex_signal(&pool->tasks_left); } @@ -186,9 +183,8 @@ work_start: } // if we've done all our work, and there's nothing to steal, go to sleep - mutex_lock(&pool->task_lock); - condition_wait(&pool->tasks_available, &pool->task_lock); - mutex_unlock(&pool->task_lock); + i32 state = pool->tasks_available.load(); + futex_wait(&pool->tasks_available, state); } return 0; diff --git a/src/threading.cpp b/src/threading.cpp index fb71a2c29..e3f26a8a0 100644 --- a/src/threading.cpp +++ b/src/threading.cpp @@ -393,7 +393,7 @@ gb_internal void thread_init(ThreadPool *pool, Thread *t, isize idx) { #endif t->capacity = 1 << 14; // must be a power of 2 - t->queue = (WorkerTask *)calloc(sizeof(WorkerTask), t->capacity); + t->queue = gb_alloc_array(heap_allocator(), WorkerTask, t->capacity); t->head_and_tail = 0; t->pool = pool; t->idx = idx; @@ -429,6 +429,8 @@ gb_internal void thread_join_and_destroy(Thread *t) { pthread_join(t->posix_handle, NULL); t->posix_handle = 0; #endif + + gb_free(heap_allocator(), t->queue); } gb_internal void thread_set_name(Thread *t, char const *name) { -- cgit v1.2.3 From da479c7628d827d4343f82954c7d09adff31876c Mon Sep 17 00:00:00 2001 From: gingerBill Date: Mon, 2 Jan 2023 00:35:12 +0000 Subject: Minor style change --- src/thread_pool.cpp | 6 ++---- src/threading.cpp | 4 ---- 2 files changed, 2 insertions(+), 8 deletions(-) (limited to 'src/threading.cpp') diff --git a/src/thread_pool.cpp b/src/thread_pool.cpp index 768a92645..9ac1af039 100644 --- a/src/thread_pool.cpp +++ b/src/thread_pool.cpp @@ -61,9 +61,7 @@ void thread_pool_queue_push(Thread *thread, WorkerTask task) { u64 tail = ((u32)capture) & mask; u64 new_head = (head + 1) & mask; - if (new_head == tail) { - GB_PANIC("Thread Queue Full!\n"); - } + GB_ASSERT_MSG(new_head != tail, "Thread Queue Full!"); // This *must* be done in here, to avoid a potential race condition where we no longer own the slot by the time we're assigning thread->queue[head] = task; @@ -139,7 +137,7 @@ gb_internal THREAD_PROC(thread_pool_thread_proc) { for (;;) { work_start: - if (!pool->running) { + if (!pool->running.load()) { break; } diff --git a/src/threading.cpp b/src/threading.cpp index e3f26a8a0..4c7aa8f92 100644 --- a/src/threading.cpp +++ b/src/threading.cpp @@ -193,10 +193,6 @@ gb_internal void semaphore_wait(Semaphore *s) { CONDITION_VARIABLE cond; }; - gb_internal void condition_init(Condition *c) { - } - gb_internal void condition_destroy(Condition *c) { - } gb_internal void condition_broadcast(Condition *c) { WakeAllConditionVariable(&c->cond); } -- cgit v1.2.3 From c293f5b7ebc3b733e996a97c6e32d678f13b3ee5 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Mon, 2 Jan 2023 16:56:05 +0000 Subject: Remove unneeded mutex --- src/check_expr.cpp | 33 +++++++++++++++++---------------- src/checker.hpp | 7 ++++++- src/common_memory.cpp | 18 ++++++------------ src/llvm_backend_stmt.cpp | 5 ++--- src/main.cpp | 3 +-- src/threading.cpp | 17 +++++++++-------- 6 files changed, 41 insertions(+), 42 deletions(-) (limited to 'src/threading.cpp') diff --git a/src/check_expr.cpp b/src/check_expr.cpp index 5445e73c7..f47361c27 100644 --- a/src/check_expr.cpp +++ b/src/check_expr.cpp @@ -193,8 +193,7 @@ gb_internal void check_did_you_mean_objc_entity(String const &name, Entity *e, b GB_ASSERT(e->kind == Entity_TypeName); GB_ASSERT(e->TypeName.objc_metadata != nullptr); auto *objc_metadata = e->TypeName.objc_metadata; - mutex_lock(objc_metadata->mutex); - defer (mutex_unlock(objc_metadata->mutex)); + MUTEX_GUARD(objc_metadata->mutex); StringSet set = {}; string_set_init(&set, heap_allocator()); @@ -369,8 +368,7 @@ gb_internal bool find_or_generate_polymorphic_procedure(CheckerContext *old_c, E GB_ASSERT(dst == nullptr); } - mutex_lock(&info->gen_procs_mutex); - defer (mutex_unlock(&info->gen_procs_mutex)); + // MUTEX_GUARD(&info->gen_procs_mutex); if (!src->Proc.is_polymorphic || src->Proc.is_poly_specialized) { return false; @@ -436,11 +434,14 @@ gb_internal bool find_or_generate_polymorphic_procedure(CheckerContext *old_c, E return false; } - auto *found_gen_procs = map_get(&info->gen_procs, base_entity->identifier.load()); + GenProcsData *found_gen_procs = nullptr; + + MUTEX_GUARD(&info->gen_procs_mutex); + + found_gen_procs = map_get(&info->gen_procs, base_entity->identifier.load()); if (found_gen_procs) { - auto procs = *found_gen_procs; - for_array(i, procs) { - Entity *other = procs[i]; + MUTEX_GUARD(&found_gen_procs->mutex); + for (Entity *other : found_gen_procs->procs) { Type *pt = base_type(other->type); if (are_types_identical(pt, final_proc_type)) { if (poly_proc_data) { @@ -463,15 +464,13 @@ gb_internal bool find_or_generate_polymorphic_procedure(CheckerContext *old_c, E // LEAK TODO(bill): Cloning this AST may be leaky Ast *cloned_proc_type_node = clone_ast(pt->node); success = check_procedure_type(&nctx, final_proc_type, cloned_proc_type_node, &operands); - if (!success) { return false; } if (found_gen_procs) { - auto procs = *found_gen_procs; - for_array(i, procs) { - Entity *other = procs[i]; + MUTEX_GUARD(&found_gen_procs->mutex); + for (Entity *other : found_gen_procs->procs) { Type *pt = base_type(other->type); if (are_types_identical(pt, final_proc_type)) { if (poly_proc_data) { @@ -567,11 +566,13 @@ gb_internal bool find_or_generate_polymorphic_procedure(CheckerContext *old_c, E proc_info->poly_def_node = poly_def_node; if (found_gen_procs) { - array_add(found_gen_procs, entity); + MUTEX_GUARD(&found_gen_procs->mutex); + array_add(&found_gen_procs->procs, entity); } else { - auto array = array_make(heap_allocator()); - array_add(&array, entity); - map_set(&info->gen_procs, base_entity->identifier.load(), array); + GenProcsData gen_proc_data = {}; + gen_proc_data.procs = array_make(heap_allocator()); + array_add(&gen_proc_data.procs, entity); + map_set(&info->gen_procs, base_entity->identifier.load(), gen_proc_data); } if (poly_proc_data) { diff --git a/src/checker.hpp b/src/checker.hpp index 37aff41b1..56f8707d3 100644 --- a/src/checker.hpp +++ b/src/checker.hpp @@ -311,6 +311,11 @@ struct LoadFileCache { StringMap hashes; }; +struct GenProcsData { + Array procs; + BlockingMutex mutex; +}; + // CheckerInfo stores all the symbol information for a type-checked program struct CheckerInfo { Checker *checker; @@ -360,7 +365,7 @@ struct CheckerInfo { RecursiveMutex gen_procs_mutex; RecursiveMutex gen_types_mutex; - PtrMap > gen_procs; // Key: Ast * | Identifier -> Entity + PtrMap gen_procs; // Key: Ast * | Identifier -> Entity PtrMap > gen_types; BlockingMutex type_info_mutex; // NOT recursive diff --git a/src/common_memory.cpp b/src/common_memory.cpp index 2022554cf..cdf2281fe 100644 --- a/src/common_memory.cpp +++ b/src/common_memory.cpp @@ -37,7 +37,6 @@ gb_internal gb_inline void *align_formula_ptr(void *ptr, isize align) { gb_global BlockingMutex global_memory_block_mutex; -gb_global BlockingMutex global_memory_allocator_mutex; gb_internal void platform_virtual_memory_init(void); @@ -55,9 +54,9 @@ struct MemoryBlock { }; struct Arena { - MemoryBlock *curr_block; - isize minimum_block_size; - bool ignore_mutex; + MemoryBlock * curr_block; + isize minimum_block_size; + BlockingMutex mutex; }; enum { DEFAULT_MINIMUM_BLOCK_SIZE = 8ll*1024ll*1024ll }; @@ -83,10 +82,7 @@ gb_internal isize arena_align_forward_offset(Arena *arena, isize alignment) { gb_internal void *arena_alloc(Arena *arena, isize min_size, isize alignment) { GB_ASSERT(gb_is_power_of_two(alignment)); - BlockingMutex *mutex = &global_memory_allocator_mutex; - if (!arena->ignore_mutex) { - mutex_lock(mutex); - } + mutex_lock(&arena->mutex); isize size = 0; if (arena->curr_block != nullptr) { @@ -113,9 +109,7 @@ gb_internal void *arena_alloc(Arena *arena, isize min_size, isize alignment) { curr_block->used += size; GB_ASSERT(curr_block->used <= curr_block->size); - if (!arena->ignore_mutex) { - mutex_unlock(mutex); - } + mutex_unlock(&arena->mutex); // NOTE(bill): memory will be zeroed by default due to virtual memory return ptr; @@ -304,7 +298,7 @@ gb_internal GB_ALLOCATOR_PROC(arena_allocator_proc) { } -gb_global gb_thread_local Arena permanent_arena = {nullptr, DEFAULT_MINIMUM_BLOCK_SIZE, true}; +gb_global gb_thread_local Arena permanent_arena = {nullptr, DEFAULT_MINIMUM_BLOCK_SIZE}; gb_internal gbAllocator permanent_allocator() { return arena_allocator(&permanent_arena); } diff --git a/src/llvm_backend_stmt.cpp b/src/llvm_backend_stmt.cpp index 06abebc78..8742423a5 100644 --- a/src/llvm_backend_stmt.cpp +++ b/src/llvm_backend_stmt.cpp @@ -57,9 +57,8 @@ gb_internal void lb_build_constant_value_decl(lbProcedure *p, AstValueDecl *vd) if (pl->body != nullptr) { auto *found = map_get(&info->gen_procs, ident); if (found) { - auto procs = *found; - for_array(i, procs) { - Entity *e = procs[i]; + MUTEX_GUARD(&found->mutex); + for (Entity *e : found->procs) { if (!ptr_set_exists(min_dep_set, e)) { continue; } diff --git a/src/main.cpp b/src/main.cpp index 42d6f8e87..ad9d6b0ef 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -17,8 +17,7 @@ gb_global ThreadPool global_thread_pool; gb_internal void init_global_thread_pool(void) { isize thread_count = gb_max(build_context.thread_count, 1); - isize worker_count = thread_count-1; // NOTE(bill): The main thread will also be used for work - thread_pool_init(&global_thread_pool, permanent_allocator(), worker_count, "ThreadPoolWorker"); + thread_pool_init(&global_thread_pool, permanent_allocator(), thread_count, "ThreadPoolWorker"); } gb_internal bool thread_pool_add_task(WorkerTaskProc *proc, void *data) { return thread_pool_add_task(&global_thread_pool, proc, data); diff --git a/src/threading.cpp b/src/threading.cpp index 4c7aa8f92..c5db5d1b4 100644 --- a/src/threading.cpp +++ b/src/threading.cpp @@ -77,22 +77,23 @@ gb_internal void yield_process(void); struct MutexGuard { - MutexGuard() = delete; + MutexGuard() = delete; MutexGuard(MutexGuard const &) = delete; + MutexGuard(MutexGuard &&) = delete; - MutexGuard(BlockingMutex *bm) : bm{bm} { + explicit MutexGuard(BlockingMutex *bm) noexcept : bm{bm} { mutex_lock(this->bm); } - MutexGuard(RecursiveMutex *rm) : rm{rm} { + explicit MutexGuard(RecursiveMutex *rm) noexcept : rm{rm} { mutex_lock(this->rm); } - MutexGuard(BlockingMutex &bm) : bm{&bm} { + explicit MutexGuard(BlockingMutex &bm) noexcept : bm{&bm} { mutex_lock(this->bm); } - MutexGuard(RecursiveMutex &rm) : rm{&rm} { + explicit MutexGuard(RecursiveMutex &rm) noexcept : rm{&rm} { mutex_lock(this->rm); } - ~MutexGuard() { + ~MutexGuard() noexcept { if (this->bm) { mutex_unlock(this->bm); } else if (this->rm) { @@ -100,14 +101,14 @@ struct MutexGuard { } } - operator bool() const { return true; } + operator bool() const noexcept { return true; } BlockingMutex *bm; RecursiveMutex *rm; }; #define MUTEX_GUARD_BLOCK(m) if (MutexGuard GB_DEFER_3(_mutex_guard_){m}) -#define MUTEX_GUARD(m) MutexGuard GB_DEFER_3(_mutex_guard_){m} +#define MUTEX_GUARD(m) mutex_lock(m); defer (mutex_unlock(m)) struct RecursiveMutex { -- cgit v1.2.3 From 9737b65d9c2c4c09fd1a0ec1daa3dd7dcdeb7dc5 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Mon, 2 Jan 2023 17:18:59 +0000 Subject: Explicitly call `store` for futex --- src/threading.cpp | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) (limited to 'src/threading.cpp') diff --git a/src/threading.cpp b/src/threading.cpp index c5db5d1b4..169b9ff43 100644 --- a/src/threading.cpp +++ b/src/threading.cpp @@ -117,7 +117,8 @@ struct RecursiveMutex { }; gb_internal void mutex_lock(RecursiveMutex *m) { - Futex tid = cast(i32)thread_current_id(); + Futex tid; + tid.store(cast(i32)thread_current_id()); for (;;) { i32 prev_owner = 0; m->owner.compare_exchange_strong(prev_owner, tid, std::memory_order_acquire, std::memory_order_acquire); @@ -130,7 +131,8 @@ gb_internal void mutex_lock(RecursiveMutex *m) { } } gb_internal bool mutex_try_lock(RecursiveMutex *m) { - Futex tid = cast(i32)thread_current_id(); + Futex tid; + tid.store(cast(i32)thread_current_id()); i32 prev_owner = 0; m->owner.compare_exchange_strong(prev_owner, tid, std::memory_order_acquire, std::memory_order_acquire); if (prev_owner == 0 || prev_owner == tid) { -- cgit v1.2.3 From 0e040be9411328d2e82556b7a37fa1cf90b666bd Mon Sep 17 00:00:00 2001 From: gingerBill Date: Mon, 2 Jan 2023 17:49:16 +0000 Subject: Add define for darwin --- src/threading.cpp | 1 + 1 file changed, 1 insertion(+) (limited to 'src/threading.cpp') diff --git a/src/threading.cpp b/src/threading.cpp index 169b9ff43..bcbdaf083 100644 --- a/src/threading.cpp +++ b/src/threading.cpp @@ -641,6 +641,7 @@ gb_internal void futex_broadcast(Futex *addr) { gb_internal void futex_wait(Futex *addr, Footex val) { for (;;) { + enum { ULF_WAKE_ALL = 0x00000100 }; int ret = __ulock_wait(UL_COMPARE_AND_WAIT | ULF_NO_ERRNO | ULF_WAKE_ALL, addr, val, 0); if (ret >= 0) { if (*addr != val) { -- cgit v1.2.3 From 52b319dbfd94a223f205c1078fb98d93fc6a60e0 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Mon, 2 Jan 2023 21:53:41 +0000 Subject: Fix darwin's futex implementation in the compiler --- src/threading.cpp | 47 +++++++++++++++++++++++------------------------ 1 file changed, 23 insertions(+), 24 deletions(-) (limited to 'src/threading.cpp') diff --git a/src/threading.cpp b/src/threading.cpp index bcbdaf083..cda8fe89b 100644 --- a/src/threading.cpp +++ b/src/threading.cpp @@ -548,9 +548,9 @@ gb_internal void futex_wait(Futex *addr, Footex val) { #include -gb_internal void futex_signal(Futex *addr) { +gb_internal void futex_signal(Futex *f) { for (;;) { - int ret = futex((volatile uint32_t *)addr, FUTEX_WAKE | FUTEX_PRIVATE_FLAG, 1, NULL, NULL); + int ret = futex((volatile uint32_t *)f, FUTEX_WAKE | FUTEX_PRIVATE_FLAG, 1, NULL, NULL); if (ret == -1) { if (errno == ETIMEDOUT || errno == EINTR) { continue; @@ -565,9 +565,9 @@ gb_internal void futex_signal(Futex *addr) { } -gb_internal void futex_broadcast(Futex *addr) { +gb_internal void futex_broadcast(Futex *f) { for (;;) { - int ret = futex((volatile uint32_t *)addr, FUTEX_WAKE | FUTEX_PRIVATE_FLAG, INT32_MAX, NULL, NULL); + int ret = futex((volatile uint32_t *)f, FUTEX_WAKE | FUTEX_PRIVATE_FLAG, INT32_MAX, NULL, NULL); if (ret == -1) { if (errno == ETIMEDOUT || errno == EINTR) { continue; @@ -581,11 +581,11 @@ gb_internal void futex_broadcast(Futex *addr) { } } -gb_internal void futex_wait(Futex *addr, Footex val) { +gb_internal void futex_wait(Futex *f, Footex val) { for (;;) { - int ret = futex((volatile uint32_t *)addr, FUTEX_WAIT | FUTEX_PRIVATE_FLAG, val, NULL, NULL); + int ret = futex((volatile uint32_t *)f, FUTEX_WAIT | FUTEX_PRIVATE_FLAG, val, NULL, NULL); if (ret == -1) { - if (*addr != val) { + if (*f != val) { return; } @@ -607,9 +607,9 @@ gb_internal void futex_wait(Futex *addr, Footex val) { extern "C" int __ulock_wait(uint32_t operation, void *addr, uint64_t value, uint32_t timeout); /* timeout is specified in microseconds */ extern "C" int __ulock_wake(uint32_t operation, void *addr, uint64_t wake_value); -gb_internal void futex_signal(Futex *addr) { +gb_internal void futex_signal(Futex *f) { for (;;) { - int ret = __ulock_wake(UL_COMPARE_AND_WAIT | ULF_NO_ERRNO, addr, 0); + int ret = __ulock_wake(UL_COMPARE_AND_WAIT | ULF_NO_ERRNO, f, 0); if (ret >= 0) { return; } @@ -623,9 +623,10 @@ gb_internal void futex_signal(Futex *addr) { } } -gb_internal void futex_broadcast(Futex *addr) { +gb_internal void futex_broadcast(Futex *f) { for (;;) { - int ret = __ulock_wake(UL_COMPARE_AND_WAIT | ULF_NO_ERRNO, addr, 0); + enum { ULF_WAKE_ALL = 0x00000100 }; + int ret = __ulock_wake(UL_COMPARE_AND_WAIT | ULF_NO_ERRNO | ULF_WAKE_ALL, f, 0); if (ret >= 0) { return; } @@ -639,12 +640,11 @@ gb_internal void futex_broadcast(Futex *addr) { } } -gb_internal void futex_wait(Futex *addr, Footex val) { +gb_internal void futex_wait(Futex *f, Footex val) { for (;;) { - enum { ULF_WAKE_ALL = 0x00000100 }; - int ret = __ulock_wait(UL_COMPARE_AND_WAIT | ULF_NO_ERRNO | ULF_WAKE_ALL, addr, val, 0); + int ret = __ulock_wait(UL_COMPARE_AND_WAIT | ULF_NO_ERRNO, f, val, 0); if (ret >= 0) { - if (*addr != val) { + if (*f != val) { return; } continue; @@ -661,19 +661,18 @@ gb_internal void futex_wait(Futex *addr, Footex val) { } #elif defined(GB_SYSTEM_WINDOWS) -gb_internal void futex_signal(Futex *addr) { - WakeByAddressSingle((void *)addr); +gb_internal void futex_signal(Futex *f) { + WakeByAddressSingle(f); } -gb_internal void futex_broadcast(Futex *addr) { - WakeByAddressAll((void *)addr); +gb_internal void futex_broadcast(Futex *f) { + WakeByAddressAll(f); } -gb_internal void futex_wait(Futex *addr, Footex val) { - for (;;) { - WaitOnAddress(addr, (void *)&val, sizeof(val), INFINITE); - if (*addr != val) break; - } +gb_internal void futex_wait(Futex *f, Footex val) { + do { + WaitOnAddress(f, (void *)&val, sizeof(val), INFINITE); + } while (f->load() == val); } #endif -- cgit v1.2.3 From bc9ee8e1a4ce797a894e5648fa92216c212b6999 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Mon, 2 Jan 2023 22:13:49 +0000 Subject: Remove loops within futex signals on Linux --- src/check_decl.cpp | 2 +- src/threading.cpp | 24 ++++++++---------------- 2 files changed, 9 insertions(+), 17 deletions(-) (limited to 'src/threading.cpp') diff --git a/src/check_decl.cpp b/src/check_decl.cpp index 32d50e36d..2b6868f05 100644 --- a/src/check_decl.cpp +++ b/src/check_decl.cpp @@ -1471,7 +1471,7 @@ gb_internal bool check_proc_body(CheckerContext *ctx_, Token token, DeclInfo *de continue; } if (is_blank_ident(e->token)) { - error(e->token, "'using' a procedure parameter requires a non blank identifier"); + error(e->token, "'using' a procedure parameter requires a non blank identifier"); break; } diff --git a/src/threading.cpp b/src/threading.cpp index cda8fe89b..aca77cd8f 100644 --- a/src/threading.cpp +++ b/src/threading.cpp @@ -472,26 +472,18 @@ gb_internal void thread_set_name(Thread *t, char const *name) { #include gb_internal void futex_signal(Futex *addr) { - for (;;) { - int ret = syscall(SYS_futex, addr, FUTEX_WAKE | FUTEX_PRIVATE_FLAG, 1, NULL, NULL, 0); - if (ret == -1) { - perror("Futex wake"); - GB_PANIC("Failed in futex wake!\n"); - } else if (ret > 0) { - return; - } + int ret = syscall(SYS_futex, addr, FUTEX_WAKE | FUTEX_PRIVATE_FLAG, 1, NULL, NULL, 0); + if (ret == -1) { + perror("Futex wake"); + GB_PANIC("Failed in futex wake!\n"); } } gb_internal void futex_broadcast(Futex *addr) { - for (;;) { - int ret = syscall(SYS_futex, addr, FUTEX_WAKE | FUTEX_PRIVATE_FLAG, INT32_MAX, NULL, NULL, 0); - if (ret == -1) { - perror("Futex wake"); - GB_PANIC("Failed in futex wake!\n"); - } else if (ret > 0) { - return; - } + int ret = syscall(SYS_futex, addr, FUTEX_WAKE | FUTEX_PRIVATE_FLAG, INT32_MAX, NULL, NULL, 0); + if (ret == -1) { + perror("Futex wake"); + GB_PANIC("Failed in futex wake!\n"); } } -- cgit v1.2.3 From 0fb3032b731b640a2d0d1d62b9f8dd548e224b0e Mon Sep 17 00:00:00 2001 From: gingerBill Date: Tue, 3 Jan 2023 14:45:09 +0000 Subject: General improves to `alloc_ast_node` and other unnecessary checks --- src/common.cpp | 2 +- src/main.cpp | 4 ++-- src/parser.cpp | 4 +--- src/parser.hpp | 5 ++--- src/ptr_map.cpp | 6 ++++-- src/thread_pool.cpp | 6 +++--- src/threading.cpp | 1 + src/types.cpp | 4 ++-- 8 files changed, 16 insertions(+), 16 deletions(-) (limited to 'src/threading.cpp') diff --git a/src/common.cpp b/src/common.cpp index 199a263a1..988a992d0 100644 --- a/src/common.cpp +++ b/src/common.cpp @@ -43,9 +43,9 @@ gb_internal void debugf(char const *fmt, ...); #error Odin on Windows requires a 64-bit build-system. The 'Developer Command Prompt' for VS still defaults to 32-bit shell. The 64-bit shell can be found under the name 'x64 Native Tools Command Prompt' for VS. For more information, please see https://odin-lang.org/docs/install/#for-windows #endif -#include "threading.cpp" #include "unicode.cpp" #include "array.cpp" +#include "threading.cpp" #include "queue.cpp" #include "common_memory.cpp" #include "string.cpp" diff --git a/src/main.cpp b/src/main.cpp index 7ac78241e..c07d2c400 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -13,11 +13,11 @@ #endif #include "exact_value.cpp" #include "build_settings.cpp" - gb_global ThreadPool global_thread_pool; gb_internal void init_global_thread_pool(void) { isize thread_count = gb_max(build_context.thread_count, 1); - thread_pool_init(&global_thread_pool, permanent_allocator(), thread_count, "ThreadPoolWorker"); + isize worker_count = thread_count-1; + thread_pool_init(&global_thread_pool, permanent_allocator(), worker_count, "ThreadPoolWorker"); } gb_internal bool thread_pool_add_task(WorkerTaskProc *proc, void *data) { return thread_pool_add_task(&global_thread_pool, proc, data); diff --git a/src/parser.cpp b/src/parser.cpp index 046469c16..c6f35d326 100644 --- a/src/parser.cpp +++ b/src/parser.cpp @@ -64,11 +64,9 @@ gb_global std::atomic global_total_node_memory_allocated; // NOTE(bill): And this below is why is I/we need a new language! Discriminated unions are a pain in C/C++ gb_internal Ast *alloc_ast_node(AstFile *f, AstKind kind) { - gbAllocator a = ast_allocator(f); - isize size = ast_node_size(kind); - Ast *node = cast(Ast *)gb_alloc(a, size); + Ast *node = cast(Ast *)arena_alloc(&global_thread_local_ast_arena, size, 16); node->kind = kind; node->file_id = f ? f->id : 0; diff --git a/src/parser.hpp b/src/parser.hpp index b492cfa85..d81194831 100644 --- a/src/parser.hpp +++ b/src/parser.hpp @@ -821,9 +821,8 @@ gb_internal gb_inline bool is_ast_when_stmt(Ast *node) { gb_global gb_thread_local Arena global_thread_local_ast_arena = {}; -gb_internal gbAllocator ast_allocator(AstFile *f) { - Arena *arena = &global_thread_local_ast_arena; - return arena_allocator(arena); +gb_internal gb_inline gbAllocator ast_allocator(AstFile *f) { + return arena_allocator(&global_thread_local_ast_arena); } gb_internal Ast *alloc_ast_node(AstFile *f, AstKind kind); diff --git a/src/ptr_map.cpp b/src/ptr_map.cpp index 083cd6697..264136881 100644 --- a/src/ptr_map.cpp +++ b/src/ptr_map.cpp @@ -27,6 +27,7 @@ struct PtrMap { gb_internal gb_inline u32 ptr_map_hash_key(uintptr key) { + u32 res; #if defined(GB_ARCH_64_BIT) key = (~key) + (key << 21); key = key ^ (key >> 24); @@ -34,12 +35,13 @@ gb_internal gb_inline u32 ptr_map_hash_key(uintptr key) { key = key ^ (key >> 14); key = (key + (key << 2)) + (key << 4); key = key ^ (key << 28); - return cast(u32)key; + res = cast(u32)key; #elif defined(GB_ARCH_32_BIT) u32 state = ((u32)key) * 747796405u + 2891336453u; u32 word = ((state >> ((state >> 28u) + 4u)) ^ state) * 277803737u; - return (word >> 22u) ^ word; + res = (word >> 22u) ^ word; #endif + return res ^ (res == MAP_SENTINEL); } gb_internal gb_inline u32 ptr_map_hash_key(void const *key) { return ptr_map_hash_key((uintptr)key); diff --git a/src/thread_pool.cpp b/src/thread_pool.cpp index 07ab3d323..276e93dff 100644 --- a/src/thread_pool.cpp +++ b/src/thread_pool.cpp @@ -5,7 +5,7 @@ struct ThreadPool; gb_thread_local Thread *current_thread; -gb_internal void thread_pool_init(ThreadPool *pool, gbAllocator const &a, isize thread_count, char const *worker_name); +gb_internal void thread_pool_init(ThreadPool *pool, gbAllocator const &a, isize worker_count, char const *worker_name); gb_internal void thread_pool_destroy(ThreadPool *pool); gb_internal bool thread_pool_add_task(ThreadPool *pool, WorkerTaskProc *proc, void *data); gb_internal void thread_pool_wait(ThreadPool *pool); @@ -25,9 +25,9 @@ gb_internal isize current_thread_index(void) { return current_thread ? current_thread->idx : 0; } -gb_internal void thread_pool_init(ThreadPool *pool, gbAllocator const &a, isize thread_count, char const *worker_name) { +gb_internal void thread_pool_init(ThreadPool *pool, gbAllocator const &a, isize worker_count, char const *worker_name) { pool->allocator = a; - slice_init(&pool->threads, a, thread_count + 1); + slice_init(&pool->threads, a, worker_count + 1); // NOTE: this needs to be initialized before any thread starts pool->running.store(true, std::memory_order_seq_cst); diff --git a/src/threading.cpp b/src/threading.cpp index aca77cd8f..78943150e 100644 --- a/src/threading.cpp +++ b/src/threading.cpp @@ -398,6 +398,7 @@ gb_internal void thread_init(ThreadPool *pool, Thread *t, isize idx) { t->idx = idx; } + gb_internal void thread_init_and_start(ThreadPool *pool, Thread *t, isize idx) { thread_init(pool, t, idx); isize stack_size = 0; diff --git a/src/types.cpp b/src/types.cpp index d33c36e94..fa7c1d7f7 100644 --- a/src/types.cpp +++ b/src/types.cpp @@ -2535,13 +2535,13 @@ gb_internal bool are_types_identical_internal(Type *x, Type *y, bool check_tuple if (x->kind == Type_Named) { Entity *e = x->Named.type_name; - if (e != nullptr && e->kind == Entity_TypeName && e->TypeName.is_type_alias) { + if (e->TypeName.is_type_alias) { x = x->Named.base; } } if (y->kind == Type_Named) { Entity *e = y->Named.type_name; - if (e != nullptr && e->kind == Entity_TypeName && e->TypeName.is_type_alias) { + if (e->TypeName.is_type_alias) { y = y->Named.base; } } -- cgit v1.2.3 From c7a704d345e9bda38da18807a1d7cd5bc5accc17 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Tue, 3 Jan 2023 15:26:47 +0000 Subject: Use `RwMutex` for the `Scope` --- src/check_decl.cpp | 12 ++++--- src/check_expr.cpp | 4 ++- src/check_stmt.cpp | 5 ++- src/checker.cpp | 21 +++++++----- src/checker.hpp | 2 +- src/thread_pool.cpp | 27 ++++++++------- src/threading.cpp | 96 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 7 files changed, 138 insertions(+), 29 deletions(-) (limited to 'src/threading.cpp') diff --git a/src/check_decl.cpp b/src/check_decl.cpp index 66f16546c..4afde6e51 100644 --- a/src/check_decl.cpp +++ b/src/check_decl.cpp @@ -381,8 +381,8 @@ gb_internal void override_entity_in_scope(Entity *original_entity, Entity *new_e if (found_scope == nullptr) { return; } - mutex_lock(&found_scope->mutex); - defer (mutex_unlock(&found_scope->mutex)); + rw_mutex_lock(&found_scope->mutex); + defer (rw_mutex_unlock(&found_scope->mutex)); // IMPORTANT NOTE(bill, 2021-04-10): Overriding behaviour was flawed in that the // original entity was still used check checked, but the checking was only @@ -1478,7 +1478,8 @@ gb_internal bool check_proc_body(CheckerContext *ctx_, Token token, DeclInfo *de if (t->kind == Type_Struct) { Scope *scope = t->Struct.scope; GB_ASSERT(scope != nullptr); - MUTEX_GUARD_BLOCK(scope->mutex) for (auto const &entry : scope->elements) { + rw_mutex_lock(&scope->mutex); + for (auto const &entry : scope->elements) { Entity *f = entry.value; if (f->kind == Entity_Variable) { Entity *uvar = alloc_entity_using_variable(e, f->token, f->type, nullptr); @@ -1488,6 +1489,7 @@ gb_internal bool check_proc_body(CheckerContext *ctx_, Token token, DeclInfo *de array_add(&using_entities, puv); } } + rw_mutex_unlock(&scope->mutex); } else { error(e->token, "'using' can only be applied to variables of type struct"); break; @@ -1496,7 +1498,8 @@ gb_internal bool check_proc_body(CheckerContext *ctx_, Token token, DeclInfo *de } } - MUTEX_GUARD_BLOCK(ctx->scope->mutex) for (auto const &entry : using_entities) { + rw_mutex_lock(&ctx->scope->mutex); + for (auto const &entry : using_entities) { Entity *e = entry.e; Entity *uvar = entry.uvar; Entity *prev = scope_insert_no_mutex(ctx->scope, uvar); @@ -1506,6 +1509,7 @@ gb_internal bool check_proc_body(CheckerContext *ctx_, Token token, DeclInfo *de break; } } + rw_mutex_unlock(&ctx->scope->mutex); bool where_clause_ok = evaluate_where_clauses(ctx, nullptr, decl->scope, &decl->proc_lit->ProcLit.where_clauses, !decl->where_clauses_evaluated); diff --git a/src/check_expr.cpp b/src/check_expr.cpp index c1787e7b6..d9ab328cb 100644 --- a/src/check_expr.cpp +++ b/src/check_expr.cpp @@ -236,10 +236,12 @@ gb_internal void check_did_you_mean_scope(String const &name, Scope *scope, char DidYouMeanAnswers d = did_you_mean_make(heap_allocator(), scope->elements.entries.count, name); defer (did_you_mean_destroy(&d)); - MUTEX_GUARD_BLOCK(&scope->mutex) for (auto const &entry : scope->elements) { + rw_mutex_shared_lock(&scope->mutex); + for (auto const &entry : scope->elements) { Entity *e = entry.value; did_you_mean_append(&d, e->token.string); } + rw_mutex_shared_unlock(&scope->mutex); check_did_you_mean_print(&d, prefix); } diff --git a/src/check_stmt.cpp b/src/check_stmt.cpp index e075297a4..6e84d0789 100644 --- a/src/check_stmt.cpp +++ b/src/check_stmt.cpp @@ -622,7 +622,10 @@ gb_internal bool check_using_stmt_entity(CheckerContext *ctx, AstUsingStmt *us, case Entity_ImportName: { Scope *scope = e->ImportName.scope; - MUTEX_GUARD_BLOCK(scope->mutex) for (auto const &entry : scope->elements) { + rw_mutex_lock(&scope->mutex); + defer (rw_mutex_unlock(&scope->mutex)); + + for (auto const &entry : scope->elements) { String name = entry.key.string; Entity *decl = entry.value; if (!is_entity_exported(decl)) continue; diff --git a/src/checker.cpp b/src/checker.cpp index 0075fa543..1d536074d 100644 --- a/src/checker.cpp +++ b/src/checker.cpp @@ -51,10 +51,11 @@ gb_internal bool check_rtti_type_disallowed(Ast *expr, Type *type, char const *f gb_internal void scope_reset(Scope *scope) { if (scope == nullptr) return; - MUTEX_GUARD(&scope->mutex); + rw_mutex_lock(&scope->mutex); scope->head_child.store(nullptr, std::memory_order_relaxed); string_map_clear(&scope->elements); ptr_set_clear(&scope->imported); + rw_mutex_unlock(&scope->mutex); } gb_internal void scope_reserve(Scope *scope, isize capacity) { @@ -180,9 +181,9 @@ gb_internal void init_decl_info(DeclInfo *d, Scope *scope, DeclInfo *parent) { gb_zero_item(d); d->parent = parent; d->scope = scope; - ptr_set_init(&d->deps); - ptr_set_init(&d->type_info_deps); - array_init (&d->labels, heap_allocator()); + ptr_set_init(&d->deps, 0); + ptr_set_init(&d->type_info_deps, 0); + d->labels.allocator = heap_allocator(); } gb_internal DeclInfo *make_decl_info(Scope *scope, DeclInfo *parent) { @@ -394,9 +395,9 @@ gb_internal void scope_lookup_parent(Scope *scope, String const &name, Scope **s StringHashKey key = string_hash_string(name); for (Scope *s = scope; s != nullptr; s = s->parent) { Entity **found = nullptr; - mutex_lock(&s->mutex); + rw_mutex_shared_lock(&s->mutex); found = string_map_get(&s->elements, key); - mutex_unlock(&s->mutex); + rw_mutex_shared_unlock(&s->mutex); if (found) { Entity *e = *found; if (gone_thru_proc) { @@ -482,7 +483,7 @@ gb_internal Entity *scope_insert_with_name(Scope *s, String const &name, Entity Entity **found = nullptr; Entity *result = nullptr; - MUTEX_GUARD(&s->mutex); + rw_mutex_lock(&s->mutex); found = string_map_get(&s->elements, key); @@ -509,6 +510,8 @@ gb_internal Entity *scope_insert_with_name(Scope *s, String const &name, Entity entity->scope = s; } end:; + rw_mutex_unlock(&s->mutex); + return result; } @@ -669,7 +672,8 @@ gb_internal void check_scope_usage(Checker *c, Scope *scope) { Array vetted_entities = {}; array_init(&vetted_entities, heap_allocator()); - MUTEX_GUARD_BLOCK(scope->mutex) for (auto const &entry : scope->elements) { + rw_mutex_shared_lock(&scope->mutex); + for (auto const &entry : scope->elements) { Entity *e = entry.value; if (e == nullptr) continue; VettedEntity ve_unused = {}; @@ -686,6 +690,7 @@ gb_internal void check_scope_usage(Checker *c, Scope *scope) { array_add(&vetted_entities, ve_shadowed); } } + rw_mutex_shared_unlock(&scope->mutex); gb_sort(vetted_entities.data, vetted_entities.count, gb_size_of(VettedEntity), vetted_entity_variable_pos_cmp); diff --git a/src/checker.hpp b/src/checker.hpp index cc92fce28..53052d5cd 100644 --- a/src/checker.hpp +++ b/src/checker.hpp @@ -224,7 +224,7 @@ struct Scope { std::atomic next; std::atomic head_child; - BlockingMutex mutex; + RwMutex mutex; StringMap elements; PtrSet imported; diff --git a/src/thread_pool.cpp b/src/thread_pool.cpp index 276e93dff..2c369eaad 100644 --- a/src/thread_pool.cpp +++ b/src/thread_pool.cpp @@ -47,7 +47,7 @@ gb_internal void thread_pool_destroy(ThreadPool *pool) { for_array_off(i, 1, pool->threads) { Thread *t = &pool->threads[i]; - pool->tasks_available.fetch_add(1, std::memory_order_release); + pool->tasks_available.fetch_add(1, std::memory_order_relaxed); futex_broadcast(&pool->tasks_available); thread_join_and_destroy(t); } @@ -74,7 +74,7 @@ void thread_pool_queue_push(Thread *thread, WorkerTask task) { } while (!thread->head_and_tail.compare_exchange_weak(capture, new_capture)); thread->pool->tasks_left.fetch_add(1, std::memory_order_release); - thread->pool->tasks_available.fetch_add(1, std::memory_order_release); + thread->pool->tasks_available.fetch_add(1, std::memory_order_relaxed); futex_broadcast(&thread->pool->tasks_available); } @@ -82,7 +82,7 @@ bool thread_pool_queue_pop(Thread *thread, WorkerTask *task) { u64 capture; u64 new_capture; do { - capture = thread->head_and_tail.load(); + capture = thread->head_and_tail.load(std::memory_order_acquire); u64 mask = thread->capacity - 1; u64 head = (capture >> 32) & mask; @@ -97,7 +97,7 @@ bool thread_pool_queue_pop(Thread *thread, WorkerTask *task) { *task = thread->queue[tail]; new_capture = (head << 32) | new_tail; - } while (!thread->head_and_tail.compare_exchange_weak(capture, new_capture)); + } while (!thread->head_and_tail.compare_exchange_weak(capture, new_capture, std::memory_order_release)); return true; } @@ -168,22 +168,21 @@ gb_internal THREAD_PROC(thread_pool_thread_proc) { Thread *thread = &pool->threads.data[idx]; WorkerTask task; - if (!thread_pool_queue_pop(thread, &task)) { - continue; - } - task.do_work(task.data); - pool->tasks_left.fetch_sub(1, std::memory_order_release); + if (thread_pool_queue_pop(thread, &task)) { + task.do_work(task.data); + pool->tasks_left.fetch_sub(1, std::memory_order_release); - if (pool->tasks_left.load(std::memory_order_acquire) == 0) { - futex_signal(&pool->tasks_left); - } + if (pool->tasks_left.load(std::memory_order_acquire) == 0) { + futex_signal(&pool->tasks_left); + } - goto main_loop_continue; + goto main_loop_continue; + } } } // if we've done all our work, and there's nothing to steal, go to sleep - state = pool->tasks_available.load(); + state = pool->tasks_available.load(std::memory_order_acquire); futex_wait(&pool->tasks_available, state); main_loop_continue:; diff --git a/src/threading.cpp b/src/threading.cpp index 78943150e..27a17112e 100644 --- a/src/threading.cpp +++ b/src/threading.cpp @@ -8,10 +8,12 @@ struct BlockingMutex; struct RecursiveMutex; +struct RwMutex; struct Semaphore; struct Condition; struct Thread; struct ThreadPool; +struct Parker; #define THREAD_PROC(name) isize name(struct Thread *thread) gb_internal THREAD_PROC(thread_pool_thread_proc); @@ -56,6 +58,13 @@ gb_internal void mutex_lock (RecursiveMutex *m); gb_internal bool mutex_try_lock(RecursiveMutex *m); gb_internal void mutex_unlock (RecursiveMutex *m); +gb_internal void rw_mutex_lock (RwMutex *m); +gb_internal bool rw_mutex_try_lock (RwMutex *m); +gb_internal void rw_mutex_unlock (RwMutex *m); +gb_internal void rw_mutex_shared_lock (RwMutex *m); +gb_internal bool rw_mutex_try_shared_lock(RwMutex *m); +gb_internal void rw_mutex_shared_unlock (RwMutex *m); + gb_internal void semaphore_post (Semaphore *s, i32 count); gb_internal void semaphore_wait (Semaphore *s); gb_internal void semaphore_release(Semaphore *s) { semaphore_post(s, 1); } @@ -65,6 +74,10 @@ gb_internal void condition_broadcast(Condition *c); gb_internal void condition_signal(Condition *c); gb_internal void condition_wait(Condition *c, BlockingMutex *m); +gb_internal void park(Parker *p); +gb_internal void unpark_one(Parker *p); +gb_internal void unpark_all(Parker *p); + gb_internal u32 thread_current_id(void); gb_internal void thread_init (ThreadPool *pool, Thread *t, isize idx); @@ -205,6 +218,30 @@ gb_internal void semaphore_wait(Semaphore *s) { gb_internal void condition_wait(Condition *c, BlockingMutex *m) { SleepConditionVariableSRW(&c->cond, &m->srwlock, INFINITE, 0); } + + struct RwMutex { + SRWLOCK srwlock; + }; + + gb_internal void rw_mutex_lock(RwMutex *m) { + AcquireSRWLockExclusive(&m->srwlock); + } + gb_internal bool rw_mutex_try_lock(RwMutex *m) { + return !!TryAcquireSRWLockExclusive(&m->srwlock); + } + gb_internal void rw_mutex_unlock(RwMutex *m) { + ReleaseSRWLockExclusive(&m->srwlock); + } + + gb_internal void rw_mutex_shared_lock(RwMutex *m) { + AcquireSRWLockShared(&m->srwlock); + } + gb_internal bool rw_mutex_try_shared_lock(RwMutex *m) { + return !!TryAcquireSRWLockShared(&m->srwlock); + } + gb_internal void rw_mutex_shared_unlock(RwMutex *m) { + ReleaseSRWLockShared(&m->srwlock); + } #else enum Internal_Mutex_State : i32 { Internal_Mutex_State_Unlocked = 0, @@ -306,8 +343,67 @@ gb_internal void semaphore_wait(Semaphore *s) { futex_wait(&c->state(), state); mutex_lock(m); } + + struct RwMutex { + // TODO(bill): make this a proper RW mutex + BlockingMutex mutex; + }; + + gb_internal void rw_mutex_lock(RwMutex *m) { + mutex_lock(&m->mutex); + } + gb_internal bool rw_mutex_try_lock(RwMutex *m) { + return mutex_try_lock(&m->mutex); + } + gb_internal void rw_mutex_unlock(RwMutex *m) { + mutex_unlock(&m->mutex); + } + + gb_internal void rw_mutex_shared_lock(RwMutex *m) { + mutex_lock(&m->mutex); + } + gb_internal bool rw_mutex_try_shared_lock(RwMutex *m) { + return mutex_try_lock(&m->mutex); + } + gb_internal void rw_mutex_shared_unlock(RwMutex *m) { + mutex_unlock(&m->mutex); + } #endif +struct Parker { + Futex state; +}; +enum ParkerState : u32 { + ParkerState_Empty = 0, + ParkerState_Notified = 1, + ParkerState_Parked = UINT32_MAX, +}; + +gb_internal void park(Parker *p) { + if (p->state.fetch_sub(1, std::memory_order_acquire) == ParkerState_Notified) { + return; + } + for (;;) { + futex_wait(&p->state, ParkerState_Parked); + i32 notified = ParkerState_Empty; + if (p->state.compare_exchange_strong(notified, ParkerState_Empty, std::memory_order_acquire, std::memory_order_acquire)) { + return; + } + } +} + +gb_internal void unpark_one(Parker *p) { + if (p->state.exchange(ParkerState_Notified, std::memory_order_release) == ParkerState_Parked) { + futex_signal(&p->state); + } +} + +gb_internal void unpark_all(Parker *p) { + if (p->state.exchange(ParkerState_Notified, std::memory_order_release) == ParkerState_Parked) { + futex_broadcast(&p->state); + } +} + gb_internal u32 thread_current_id(void) { u32 thread_id; -- cgit v1.2.3 From d06a0e7093c3f06a474a040385f1b9dfdfce29ad Mon Sep 17 00:00:00 2001 From: gingerBill Date: Wed, 4 Jan 2023 13:30:27 +0000 Subject: Improve the `PtrSet` to be as simple and small as possible --- src/check_stmt.cpp | 1 + src/checker.cpp | 33 +++--- src/ptr_map.cpp | 2 +- src/ptr_set.cpp | 303 +++++++++++++++++++++++------------------------------ src/threading.cpp | 20 ++-- 5 files changed, 157 insertions(+), 202 deletions(-) (limited to 'src/threading.cpp') diff --git a/src/check_stmt.cpp b/src/check_stmt.cpp index 9547035d0..b4dd4cd7d 100644 --- a/src/check_stmt.cpp +++ b/src/check_stmt.cpp @@ -1289,6 +1289,7 @@ gb_internal void check_type_switch_stmt(CheckerContext *ctx, Ast *node, u32 mod_ for (Type *t : variants) { if (!type_ptr_set_exists(&seen, t)) { array_add(&unhandled, t); + gb_printf_err("HERE: %p %s\n", t, type_to_string(t)); } } diff --git a/src/checker.cpp b/src/checker.cpp index 78f96e47f..b8709f15e 100644 --- a/src/checker.cpp +++ b/src/checker.cpp @@ -66,15 +66,10 @@ gb_internal void scope_reserve(Scope *scope, isize capacity) { } gb_internal void entity_graph_node_set_destroy(EntityGraphNodeSet *s) { - if (s->hashes.data != nullptr) { - ptr_set_destroy(s); - } + ptr_set_destroy(s); } gb_internal void entity_graph_node_set_add(EntityGraphNodeSet *s, EntityGraphNode *n) { - if (s->hashes.data == nullptr) { - ptr_set_init(s); - } ptr_set_add(s, n); } @@ -2556,7 +2551,6 @@ gb_internal Array generate_entity_dependency_graph(CheckerInf } // IMPORTANT NOTE/TODO(bill, 2020-11-15): These three calls take the majority of the // the time to process - entity_graph_node_set_add(&p->succ, s); entity_graph_node_set_add(&s->pred, p); // Remove edge to 'n' @@ -2577,7 +2571,7 @@ gb_internal Array generate_entity_dependency_graph(CheckerInf for_array(i, G) { EntityGraphNode *n = G[i]; n->index = i; - n->dep_count = n->succ.entries.count; + n->dep_count = n->succ.count; GB_ASSERT(n->dep_count >= 0); } @@ -4228,7 +4222,7 @@ gb_internal Array generate_import_dependency_graph(Checker *c for (auto const &entry : M) { auto n = entry.value; n->index = i++; - n->dep_count = n->succ.entries.count; + n->dep_count = n->succ.count; GB_ASSERT(n->dep_count >= 0); array_add(&G, n); } @@ -5706,17 +5700,6 @@ gb_internal void check_parsed_files(Checker *c) { check_scope_usage(c, f->scope); } - TIME_SECTION("add untyped expression values"); - // Add untyped expression values - for (UntypedExprInfo u = {}; mpmc_dequeue(&c->global_untyped_queue, &u); /**/) { - GB_ASSERT(u.expr != nullptr && u.info != nullptr); - if (is_type_typed(u.info->type)) { - compiler_error("%s (type %s) is typed!", expr_to_string(u.expr), type_to_string(u.info->type)); - } - add_type_and_value(&c->builtin_ctx, u.expr, u.info->mode, u.info->type, u.info->value); - } - - TIME_SECTION("add basic type information"); // Add "Basic" type information for (isize i = 0; i < Basic_COUNT; i++) { @@ -5810,6 +5793,16 @@ gb_internal void check_parsed_files(Checker *c) { GB_ASSERT(c->info.entity_queue.count.load(std::memory_order_relaxed) == 0); GB_ASSERT(c->info.definition_queue.count.load(std::memory_order_relaxed) == 0); + TIME_SECTION("add untyped expression values"); + // Add untyped expression values + for (UntypedExprInfo u = {}; mpmc_dequeue(&c->global_untyped_queue, &u); /**/) { + GB_ASSERT(u.expr != nullptr && u.info != nullptr); + if (is_type_typed(u.info->type)) { + compiler_error("%s (type %s) is typed!", expr_to_string(u.expr), type_to_string(u.info->type)); + } + add_type_and_value(&c->builtin_ctx, u.expr, u.info->mode, u.info->type, u.info->value); + } + TIME_SECTION("sort init procedures"); check_sort_init_procedures(c); diff --git a/src/ptr_map.cpp b/src/ptr_map.cpp index ae3cd4b40..8869bf3fe 100644 --- a/src/ptr_map.cpp +++ b/src/ptr_map.cpp @@ -41,7 +41,7 @@ gb_internal gb_inline u32 ptr_map_hash_key(uintptr key) { u32 word = ((state >> ((state >> 28u) + 4u)) ^ state) * 277803737u; res = (word >> 22u) ^ word; #endif - return res ^ (res == MAP_SENTINEL); + return res; } gb_internal gb_inline u32 ptr_map_hash_key(void const *key) { return ptr_map_hash_key((uintptr)key); diff --git a/src/ptr_set.cpp b/src/ptr_set.cpp index e2b3f2372..8be2b0524 100644 --- a/src/ptr_set.cpp +++ b/src/ptr_set.cpp @@ -1,19 +1,22 @@ template -struct PtrSetEntry { - static_assert(sizeof(T) == sizeof(void *), "Key size must be pointer size"); - - T ptr; - MapIndex next; +struct TypeIsPointer { + enum {value = false}; +}; - operator T() const noexcept { - return this->ptr; - } +template +struct TypeIsPointer { + enum {value = true}; }; + template struct PtrSet { - Slice hashes; - Array> entries; + static_assert(TypeIsPointer::value, "PtrSet::T must be a pointer"); + static constexpr T TOMBSTONE = (T)(~uintptr(0)); + + T * keys; + usize count; + usize capacity; }; template gb_internal void ptr_set_init (PtrSet *s, isize capacity = 16); @@ -30,225 +33,183 @@ gb_internal gbAllocator ptr_set_allocator(void) { template gb_internal void ptr_set_init(PtrSet *s, isize capacity) { + GB_ASSERT(s->keys == nullptr); if (capacity != 0) { capacity = next_pow2_isize(gb_max(16, capacity)); + s->keys = gb_alloc_array(ptr_set_allocator(), T, capacity); + // This memory will be zeroed, no need to explicitly zero it } - - slice_init(&s->hashes, ptr_set_allocator(), capacity); - array_init(&s->entries, ptr_set_allocator(), 0, capacity); - for (isize i = 0; i < capacity; i++) { - s->hashes.data[i] = MAP_SENTINEL; - } + s->count = 0; + s->capacity = capacity; } template gb_internal void ptr_set_destroy(PtrSet *s) { - if (s->entries.allocator.proc == nullptr) { - s->entries.allocator = ptr_set_allocator(); - } - slice_free(&s->hashes, s->entries.allocator); - array_free(&s->entries); + gb_free(ptr_set_allocator(), s->keys); + s->keys = nullptr; + s->count = 0; + s->capacity = 0; } template -gb_internal MapIndex ptr_set__add_entry(PtrSet *s, T ptr) { - PtrSetEntry e = {}; - e.ptr = ptr; - e.next = MAP_SENTINEL; - array_add(&s->entries, e); - return cast(MapIndex)(s->entries.count-1); -} - - -template -gb_internal MapFindResult ptr_set__find(PtrSet *s, T ptr) { - MapFindResult fr = {MAP_SENTINEL, MAP_SENTINEL, MAP_SENTINEL}; - if (s->hashes.count != 0) { - u32 hash = ptr_map_hash_key(ptr); - fr.hash_index = cast(MapIndex)(hash & (s->hashes.count-1)); - fr.entry_index = s->hashes.data[fr.hash_index]; - while (fr.entry_index != MAP_SENTINEL) { - if (s->entries.data[fr.entry_index].ptr == ptr) { - return fr; +gb_internal isize ptr_set__find(PtrSet *s, T ptr) { + GB_ASSERT(ptr != nullptr); + if (s->count != 0) { + #if 0 + for (usize i = 0; i < s->capacity; i++) { + if (s->keys[i] == ptr) { + return i; } - fr.entry_prev = fr.entry_index; - fr.entry_index = s->entries.data[fr.entry_index].next; } - } - return fr; -} - -template -gb_internal MapFindResult ptr_set__find_from_entry(PtrSet *s, PtrSetEntry *e) { - MapFindResult fr = {MAP_SENTINEL, MAP_SENTINEL, MAP_SENTINEL}; - if (s->hashes.count != 0) { - u32 hash = ptr_map_hash_key(e->ptr); - fr.hash_index = cast(MapIndex)(hash & (s->hashes.count-1)); - fr.entry_index = s->hashes.data[fr.hash_index]; - while (fr.entry_index != MAP_SENTINEL) { - if (&s->entries.data[fr.entry_index] == e) { - return fr; + #else + u32 hash = ptr_map_hash_key(ptr); + usize mask = s->capacity-1; + usize hash_index = cast(usize)hash & mask; + for (usize i = 0; i < s->capacity; i++) { + T key = s->keys[hash_index]; + if (key == ptr) { + return hash_index; + } else if (key == nullptr) { + return -1; } - fr.entry_prev = fr.entry_index; - fr.entry_index = s->entries.data[fr.entry_index].next; + hash_index = (hash_index+1)&mask; } + #endif } - return fr; + return -1; } template gb_internal bool ptr_set__full(PtrSet *s) { - return 0.75f * s->hashes.count <= s->entries.count; + return 0.75f * s->capacity <= s->count; } template -gb_internal void ptr_set_reset_entries(PtrSet *s) { - for (isize i = 0; i < s->hashes.count; i++) { - s->hashes.data[i] = MAP_SENTINEL; - } - for (isize i = 0; i < s->entries.count; i++) { - MapFindResult fr; - PtrSetEntry *e = &s->entries.data[i]; - e->next = MAP_SENTINEL; - fr = ptr_set__find_from_entry(s, e); - if (fr.entry_prev == MAP_SENTINEL) { - s->hashes[fr.hash_index] = cast(MapIndex)i; - } else { - s->entries[fr.entry_prev].next = cast(MapIndex)i; - } +gb_internal gb_inline void ptr_set_grow(PtrSet *old_set) { + if (old_set->capacity == 0) { + ptr_set_init(old_set); + return; } -} -template -gb_internal void ptr_set_reserve(PtrSet *s, isize cap) { - if (s->entries.allocator.proc == nullptr) { - s->entries.allocator = ptr_set_allocator(); - } - array_reserve(&s->entries, cap); - if (s->entries.count*2 < s->hashes.count) { - return; + PtrSet new_set = {}; + ptr_set_init(&new_set, gb_max(old_set->capacity<<1, 16)); + + for (T ptr : *old_set) { + bool was_new = ptr_set_update(&new_set, ptr); + GB_ASSERT(!was_new); } - slice_resize(&s->hashes, s->entries.allocator, cap*2); - ptr_set_reset_entries(s); -} + GB_ASSERT(old_set->count == new_set.count); -template -gb_internal gb_inline void ptr_set_grow(PtrSet *s) { - isize new_count = gb_max(s->hashes.count<<1, 16); - ptr_set_reserve(s, new_count); + ptr_set_destroy(old_set); + + *old_set = new_set; } template gb_internal gb_inline bool ptr_set_exists(PtrSet *s, T ptr) { - isize index = ptr_set__find(s, ptr).entry_index; - return index != MAP_SENTINEL; + return ptr_set__find(s, ptr) >= 0; } -// Returns true if it already exists -template -gb_internal T ptr_set_add(PtrSet *s, T ptr) { - MapIndex index; - MapFindResult fr; - if (s->hashes.count == 0) { - ptr_set_grow(s); - } - fr = ptr_set__find(s, ptr); - if (fr.entry_index == MAP_SENTINEL) { - index = ptr_set__add_entry(s, ptr); - if (fr.entry_prev != MAP_SENTINEL) { - s->entries.data[fr.entry_prev].next = index; - } else { - s->hashes.data[fr.hash_index] = index; - } - } - if (ptr_set__full(s)) { - ptr_set_grow(s); - } - return ptr; -} template gb_internal bool ptr_set_update(PtrSet *s, T ptr) { // returns true if it previously existsed - bool exists = false; - MapIndex index; - MapFindResult fr; - if (s->hashes.count == 0) { + if (ptr_set_exists(s, ptr)) { + return true; + } + + if (s->keys == nullptr) { + ptr_set_init(s); + } else if (ptr_set__full(s)) { ptr_set_grow(s); } - fr = ptr_set__find(s, ptr); - if (fr.entry_index != MAP_SENTINEL) { - exists = true; - } else { - index = ptr_set__add_entry(s, ptr); - if (fr.entry_prev != MAP_SENTINEL) { - s->entries.data[fr.entry_prev].next = index; - } else { - s->hashes.data[fr.hash_index] = index; + GB_ASSERT(s->count < s->capacity); + GB_ASSERT(s->capacity >= 0); + + usize mask = s->capacity-1; + u32 hash = ptr_map_hash_key(ptr); + usize hash_index = (cast(usize)hash) & mask; + GB_ASSERT(hash_index < s->capacity); + for (usize i = 0; i < s->capacity; i++) { + T *key = &s->keys[hash_index]; + GB_ASSERT(*key != ptr); + if (*key == PtrSet::TOMBSTONE || *key == nullptr) { + *key = ptr; + s->count++; + return false; } + hash_index = (hash_index+1)&mask; } - if (ptr_set__full(s)) { - ptr_set_grow(s); - } - return exists; -} - + GB_PANIC("ptr set out of memory"); + return false; +} template -gb_internal void ptr_set__erase(PtrSet *s, MapFindResult fr) { - MapFindResult last; - if (fr.entry_prev == MAP_SENTINEL) { - s->hashes.data[fr.hash_index] = s->entries.data[fr.entry_index].next; - } else { - s->entries.data[fr.entry_prev].next = s->entries.data[fr.entry_index].next; - } - if (cast(isize)fr.entry_index == s->entries.count-1) { - array_pop(&s->entries); - return; - } - s->entries.data[fr.entry_index] = s->entries.data[s->entries.count-1]; - last = ptr_set__find(s, s->entries.data[fr.entry_index].ptr); - if (last.entry_prev != MAP_SENTINEL) { - s->entries.data[last.entry_prev].next = fr.entry_index; - } else { - s->hashes.data[last.hash_index] = fr.entry_index; - } +gb_internal T ptr_set_add(PtrSet *s, T ptr) { + ptr_set_update(s, ptr); + return ptr; } + template gb_internal void ptr_set_remove(PtrSet *s, T ptr) { - MapFindResult fr = ptr_set__find(s, ptr); - if (fr.entry_index != MAP_SENTINEL) { - ptr_set__erase(s, fr); + isize index = ptr_set__find(s, ptr); + if (index >= 0) { + GB_ASSERT(s->count > 0); + s->keys[index] = PtrSet::TOMBSTONE; + s->count--; } } template gb_internal gb_inline void ptr_set_clear(PtrSet *s) { - array_clear(&s->entries); - for (isize i = 0; i < s->hashes.count; i++) { - s->hashes.data[i] = MAP_SENTINEL; - } + s->count = 0; + gb_zero_size(s->keys, s->capacity*gb_size_of(T)); } - -template -gb_internal PtrSetEntry *begin(PtrSet &m) noexcept { - return m.entries.data; -} template -gb_internal PtrSetEntry const *begin(PtrSet const &m) noexcept { - return m.entries.data; -} +struct PtrSetIterator { + PtrSet *set; + usize index; + + PtrSetIterator &operator++() noexcept { + for (;;) { + ++index; + if (set->capacity == index) { + return *this; + } + T key = set->keys[index]; + if (key != nullptr && key != PtrSet::TOMBSTONE) { + return *this; + } + } + } + + bool operator==(PtrSetIterator const &other) const noexcept { + return this->set == other.set && this->index == other.index; + } + + + operator T *() const { + return &set->keys[index]; + } +}; template -gb_internal PtrSetEntry *end(PtrSet &m) noexcept { - return m.entries.data + m.entries.count; +gb_internal PtrSetIterator begin(PtrSet &set) noexcept { + usize index = 0; + while (index < set.capacity) { + T key = set.keys[index]; + if (key != nullptr && key != PtrSet::TOMBSTONE) { + break; + } + index++; + } + return PtrSetIterator{&set, index}; } - template -gb_internal PtrSetEntry const *end(PtrSet const &m) noexcept { - return m.entries.data + m.entries.count; +gb_internal PtrSetIterator end(PtrSet &set) noexcept { + return PtrSetIterator{&set, set.capacity}; } \ No newline at end of file diff --git a/src/threading.cpp b/src/threading.cpp index 27a17112e..bf298e024 100644 --- a/src/threading.cpp +++ b/src/threading.cpp @@ -699,13 +699,13 @@ extern "C" int __ulock_wake(uint32_t operation, void *addr, uint64_t wake_value) gb_internal void futex_signal(Futex *f) { for (;;) { int ret = __ulock_wake(UL_COMPARE_AND_WAIT | ULF_NO_ERRNO, f, 0); - if (ret >= 0) { + if (ret == 0) { return; } - if (ret == EINTR || ret == EFAULT) { + if (ret == -EINTR || ret == -EFAULT) { continue; } - if (ret == ENOENT) { + if (ret == -ENOENT) { return; } GB_PANIC("Failed in futex wake!\n"); @@ -716,13 +716,13 @@ gb_internal void futex_broadcast(Futex *f) { for (;;) { enum { ULF_WAKE_ALL = 0x00000100 }; int ret = __ulock_wake(UL_COMPARE_AND_WAIT | ULF_NO_ERRNO | ULF_WAKE_ALL, f, 0); - if (ret >= 0) { + if (ret == 0) { return; } - if (ret == EINTR || ret == EFAULT) { + if (ret == -EINTR || ret == -EFAULT) { continue; } - if (ret == ENOENT) { + if (ret == -ENOENT) { return; } GB_PANIC("Failed in futex wake!\n"); @@ -732,16 +732,16 @@ gb_internal void futex_broadcast(Futex *f) { gb_internal void futex_wait(Futex *f, Footex val) { for (;;) { int ret = __ulock_wait(UL_COMPARE_AND_WAIT | ULF_NO_ERRNO, f, val, 0); - if (ret >= 0) { + if (ret == 0) { if (*f != val) { return; } continue; } - if (ret == EINTR || ret == EFAULT) { - continue; + if (ret == -EINTR || ret == -EFAULT) { + -continue; } - if (ret == ENOENT) { + if (ret == -ENOENT) { return; } -- cgit v1.2.3