From 70831b26a1608227f7cf91a9ef07376fe4620b26 Mon Sep 17 00:00:00 2001 From: rpj Date: Tue, 28 Jul 1998 04:09:42 +0000 Subject: Tue Jul 28 14:04:29 1998 Ross Johnson * private.c: Added detailed explanation of the new thread allocation scheme. (_pthread_new_thread): Totally rewritten to use new thread allocation scheme. (_pthread_delete_thread): Ditto. (_pthread_find_thread): Obsolete. --- ChangeLog | 9 +++ private.c | 203 +++++++++++++++++++++++++++++++++++++------------------------- 2 files changed, 129 insertions(+), 83 deletions(-) diff --git a/ChangeLog b/ChangeLog index d8d18b7..f876fbe 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,12 @@ +Tue Jul 28 14:04:29 1998 Ross Johnson + + * private.c: Added detailed explanation of the new thread + allocation scheme. + (_pthread_new_thread): Totally rewritten to use + new thread allocation scheme. + (_pthread_delete_thread): Ditto. + (_pthread_find_thread): Obsolete. + Mon Jul 27 17:46:37 1998 Ross Johnson * create.c (pthread_create): Start of rewrite. Not completed yet. diff --git a/private.c b/private.c index 44afd4f..db26563 100644 --- a/private.c +++ b/private.c @@ -9,121 +9,158 @@ #include "pthread.h" #include "implement.h" -/* The threads table works as follows: - hash into the table, - if the thread in this slot doesn't match then start single - stepping from there until we find it, or we hit an empty slot, or - we end up where we started from. - - The scheme should have these characteristics: - - if the thread handle is a sequence number then the hash will - succeed first time every time, - - if the thread handle is a pseudo randomish value (eg. a pointer) - then the hash should succeed first time most times. +/* Thread ID management. + --------------------- + + We started by simply mapping the Win32 thread handle to directly to + pthread_t. Then, is order to process pthread_join()'s, needed to be + able to keep our POSIX thread ID (pthread_t) around after the Win32 + thread has terminated and possibly reused the Win32 handle. + + The pthread_t value is now actually the pointer to a thread struct: + + typedef struct _pthread * pthread_t; + + which amongst other things stores the Win32 thread handle: + + struct _pthread { + HANDLE win32handle; + int ptstatus; + ... + }; + + So now whereever we need to use the Win32 handle it can be accessed + as: + + pthread_t T = pthread_this(); + HANDLE H; + + H = T->win32handle; + + // or (which is NOT preferred, let the compiler optimise to this). + + H = (HANDLE) *T; + + + POSIX Threads Table + ------------------- + + Having the thread ID as a pointer to the thread struct itself + avoids the need to search the threads table in all but the initial + occation where we create the thread. + + Initially we used a hash function to select a free thread struct + from the table, possibly needing a walk through the table if the + hash collided with an already in-use thread. + + The scheme used now is more efficient and is done as follows: + + We use two tables and two counters: + + struct _pthread _pthread_virgins[PTHREAD_THREADS_MAX]; + pthread_t _pthread_reuse[PTHREAD_THREADS_MAX]; + + int _pthread_virgin_next = 0; + int _pthread_reuse_top = -1; + + The counter _pthread_virgin_next is an index into _pthread_virgins[], + which can be thought of as a list, and _pthread_reuse_top is an + index into _pthread_reuse[], which can be thought of as a LIFO stack. + + Once taken from _pthread_virgins[], used and freed threads are only + ever pushed back onto _pthread_reuse[]. + + The code for choosing a new (pthread_t) thread from the pool of + free thread structs looks like: + + if (_pthread_reuse_top == -1) + { + if (_pthread_virgin_next >= PTHREAD_THREADS_MAX) + { + return EAGAIN; + } + else + { + thread = _pthread_virgin[_pthread_virgin_next++]; + } + } + else + { + thread = _pthread_reuse[_pthread_reuse_top--]; + } + + + The code to free a thread is: + + _pthread_reuse[++_pthread_reuse_top] = thread; + */ int -_pthread_new_thread_entry(_pthread_t * entry) +_pthread_new_thread(pthread_t * thread) { - _pthread_t new; + pthread_t new; - if (_pthread_threads_count >= PTHREAD_THREADS_MAX) + if (_pthread_reuse_top == -1) { - return EAGAIN; - } - - /* Use a preloaded reuse stack of pthread_t. */ - new = - - while (new->thread != NULL) - { - new++; - - if (new == &_pthread_threads_table[PTHREAD_THREADS_MAX]) + if (_pthread_virgin_next >= PTHREAD_THREADS_MAX) { - /* Wrap to the top of the table. */ - new == _pthread_threads_table; + return EAGAIN; + } + else + { + new = _pthread_virgin[_pthread_virgin_next++]; } - } - - if (new->thread != NULL) - { - /* INTERNAL ERROR: There should be at least one slot left. */ - return ESRCH; } else { - new->thread = thread; - pthread_attr_init(&(new->attr)); - new->joinvalueptr = NULL; - new->cancelstate = PTHREAD_CANCEL_ENABLE; - new->canceltype = PTHREAD_CANCEL_DEFERRED; - new->cancel_pending = FALSE; - new->cleanupstack = NULL; - new->destructorstack = NULL; - new->forkpreparestack = NULL; - new->forkparentstack = NULL; - new->forkchildstack = NULL; + new = _pthread_reuse[_pthread_reuse_top--]; } - _pthread_threads_count++; - entry = new; + new->win32handle = NULL; + new->ptstatus = _PTHREAD_NEW; + pthread_attr_init(&(new->attr)); + new->joinvalueptr = NULL; + new->cancelstate = PTHREAD_CANCEL_ENABLE; + new->canceltype = PTHREAD_CANCEL_DEFERRED; + new->cancel_pending = FALSE; + new->cleanupstack = NULL; + new->destructorstack = NULL; + new->forkpreparestack = NULL; + new->forkparentstack = NULL; + new->forkchildstack = NULL; + + *thread = new; return 0; } _pthread_threads_thread * -_pthread_find_thread_entry(pthread_t thread) +_pthread_find_thread(pthread_t thread) { - _pthread_threads_thread_t * entry; - _pthread_threads_thread_t * start; - - start = entry = &_pthread_threads_table[_PTHREAD_HASH_INDEX(thread)]; - - while (entry->thread != thread) - { - entry++; - - if (entry == &_pthread_threads_table[PTHREAD_THREADS_MAX]) - { - /* Wrap to top of table. */ - entry = _pthread_threads_table; - } - } - - if (entry->thread == NULL || entry == start) - { - /* Failed to find the thread. */ - return NULL; - } - - return entry; + /* Should no longer be needed */ } -void -_pthread_delete_thread_entry(_pthread_threads_thread_t * entry) +int +_pthread_delete_thread(_pthread_t * thread) { /* We don't check that the thread has been properly cleaned up, so it had better be done already. */ /* Remove the thread entry if necessary. */ - if (entry->thread != NULL) + if (thread != NULL + && thread->ptstatus == _PTHREAD_EXITED) { pthread_attr_destroy(&(entry->attr)); - entry->thread = NULL; + thread->win32handle = NULL; + thread_ptstatus = _PTHREAD_REUSE; - if (_pthread_threads_count > 0) - { - _pthread_threads_count--; - } - else - { - /* FIXME: INTERNAL ERROR: This should not happen. */ - } + _pthread_reuse[++_pthread_reuse_top] = thread; } else { - /* FIXME: INTERNAL ERROR: This should not happen. */ + return EINVAL } + return 0; } -- cgit v1.2.3