From 85fce54e5f3c57c105123de5d4e5f4b027b5eb52 Mon Sep 17 00:00:00 2001 From: Ivan Maidanski Date: Thu, 24 Aug 2017 11:34:05 +0300 Subject: [PATCH] Eliminate most of collisions in GC_threads on Linux/x64 On some targets (e.g., Linux/x64) pthread_t values always have zero in the lowest byte (e.g. if pthread_t is actually a page-aligned pointer) thus causing all the created thread descriptors to have a collision at GC_threads[0]. This commit mixes 3 lowest bytes of thread id with a XOR operation (thus greatly reduces the probability of collisions in GC_threads). * include/private/pthread_support.h (THREAD_TABLE_SZ): Do not define if already defined; refine comment. * pthread_support.c (THREAD_TABLE_INDEX): New macro (similar to that in win32_threads.c). * pthread_support.c (GC_new_thread, GC_delete_thread, GC_delete_gc_thread, GC_lookup_thread): Replace NUMERIC_THREAD_ID(id)%THREAD_TABLE_SZ to THREAD_TABLE_INDEX(id). * pthread_support.c (GC_lookup_thread): Remove hv local variable. * win32_threads.c (THREAD_TABLE_INDEX): Replace (id>>2) to ((id>>16)^(id>>8)^id). * win32_threads.c [GC_PTHREADS] (GC_lookup_pthread): Define win32_id local variable to pass it to THREAD_TABLE_INDEX() instead of passing GET_PTHREAD_MAP_CACHE(id) directly. --- include/private/pthread_support.h | 4 +++- pthread_support.c | 16 ++++++++++------ win32_threads.c | 5 +++-- 3 files changed, 16 insertions(+), 9 deletions(-) diff --git a/include/private/pthread_support.h b/include/private/pthread_support.h index f835fa3c..4505453e 100644 --- a/include/private/pthread_support.h +++ b/include/private/pthread_support.h @@ -118,7 +118,9 @@ typedef struct GC_Thread_Rep { # endif } * GC_thread; -# define THREAD_TABLE_SZ 256 /* Must be power of 2 */ +#ifndef THREAD_TABLE_SZ +# define THREAD_TABLE_SZ 256 /* Power of 2 (for speed). */ +#endif GC_EXTERN volatile GC_thread GC_threads[THREAD_TABLE_SZ]; GC_EXTERN GC_bool GC_thr_initialized; diff --git a/pthread_support.c b/pthread_support.c index 9c973161..00032617 100644 --- a/pthread_support.c +++ b/pthread_support.c @@ -528,17 +528,22 @@ void GC_push_thread_structures(void) /* It may not be safe to allocate when we register the first thread. */ static struct GC_Thread_Rep first_thread; +#define THREAD_TABLE_INDEX(id) \ + (int)(((NUMERIC_THREAD_ID(id) >> 16) \ + ^ (NUMERIC_THREAD_ID(id) >> 8) \ + ^ NUMERIC_THREAD_ID(id)) % THREAD_TABLE_SZ) + /* Add a thread to GC_threads. We assume it wasn't already there. */ /* Caller holds allocation lock. */ STATIC GC_thread GC_new_thread(pthread_t id) { - int hv = NUMERIC_THREAD_ID(id) % THREAD_TABLE_SZ; + int hv = THREAD_TABLE_INDEX(id); GC_thread result; static GC_bool first_thread_used = FALSE; + # ifdef DEBUG_THREADS GC_log_printf("Creating thread %p\n", (void *)id); # endif - GC_ASSERT(I_HOLD_LOCK()); if (!EXPECT(first_thread_used, TRUE)) { result = &first_thread; @@ -567,7 +572,7 @@ STATIC GC_thread GC_new_thread(pthread_t id) /* It is safe to delete the main thread. */ STATIC void GC_delete_thread(pthread_t id) { - int hv = NUMERIC_THREAD_ID(id) % THREAD_TABLE_SZ; + int hv = THREAD_TABLE_INDEX(id); register GC_thread p = GC_threads[hv]; register GC_thread prev = 0; @@ -606,7 +611,7 @@ STATIC void GC_delete_thread(pthread_t id) STATIC void GC_delete_gc_thread(GC_thread t) { pthread_t id = t -> id; - int hv = NUMERIC_THREAD_ID(id) % THREAD_TABLE_SZ; + int hv = THREAD_TABLE_INDEX(id); register GC_thread p = GC_threads[hv]; register GC_thread prev = 0; @@ -639,8 +644,7 @@ STATIC void GC_delete_gc_thread(GC_thread t) /* return the most recent one. */ GC_INNER GC_thread GC_lookup_thread(pthread_t id) { - int hv = NUMERIC_THREAD_ID(id) % THREAD_TABLE_SZ; - register GC_thread p = GC_threads[hv]; + GC_thread p = GC_threads[THREAD_TABLE_INDEX(id)]; while (p != 0 && !THREAD_EQUAL(p -> id, id)) p = p -> next; return(p); diff --git a/win32_threads.c b/win32_threads.c index eaf30e47..bce8af93 100644 --- a/win32_threads.c +++ b/win32_threads.c @@ -321,7 +321,7 @@ STATIC volatile LONG GC_max_thread_index = 0; # define THREAD_TABLE_SZ 256 /* Power of 2 (for speed). */ #endif #define THREAD_TABLE_INDEX(id) /* id is of DWORD type */ \ - (int)(((id) >> 2) % THREAD_TABLE_SZ) + (int)((((id) >> 16) ^ ((id) >> 8) ^ (id)) % THREAD_TABLE_SZ) STATIC GC_thread GC_threads[THREAD_TABLE_SZ]; /* It may not be safe to allocate when we register the first thread. */ @@ -987,7 +987,8 @@ GC_API void * GC_CALL GC_call_with_gc_active(GC_fn_type fn, /* else */ { /* We first try the cache. If that fails, we use a very slow */ /* approach. */ - int hv_guess = THREAD_TABLE_INDEX(GET_PTHREAD_MAP_CACHE(id)); + DWORD win32_id = GET_PTHREAD_MAP_CACHE(id); + int hv_guess = THREAD_TABLE_INDEX(win32_id); int hv; GC_thread p; DCL_LOCK_STATE; -- 2.40.0