Multi-threading without mutexes and semaphores

Had to re-start my project because I found a fatal flaw, in doing so however I managed to come up with a way to safely use non-thread safe functions without the use of mutexes and semaphores, probably needs a bit of tweaking but I got my "Hello World!" sample to run without issues, including notifying the main thread when the child thread died, seeing how it plays with glfw & opengl later should be interesting, in either case I satisfied this is the way to go with future multi-threading code.

Hello World! :) (76a0c6ea) * Commits * Lee Shallis / Dragonbuilder * GitLab

Turned out the key was simply to use time_t to queue messages/signals, I used 3, one that only the main thread may write to but the child threads may read and vise versa for child threads, the 3rd one is for indicating to the main thread if a message has been noticed by the thread that was waiting for the next message, might not even need the thread to "resend" objects should the thread need to send a "continue" message while waiting for it's own "continue" message (that one's still to be tested, minor fix if not the case).

Finally got to the point where I'm attempting to request safe execution on anything and currently hitting an infinite wait, since I'm having a brain fart atm I might as well ask peops to have a look at my wait code and see if they can spot the issue:

Code:

---

SIGNAL * awaitInput( SIGNAL *p )
{
        SIGNAL *a = NULL;
        BRANCH *branch = GetThreadLinks(TopThread());

        while ( !a )
        {
                PauseThread();
                a = whichSignal( p, a, querySignals( branch->Init, p ) );
                a = whichSignal( p, a, querySignals( branch->Next, p ) );
        }

        return a;
}

BASIC_EXP SIG*        AwaitInput( ACT *src )
{
        ACT *top = TopThread();
        SIG *sig = GetThreadInput( src );
        SIG *out = GetThreadInput( src );
        SIG *all = GetThreadOrder( top );
        ucap val = 0;

        if ( src == top )
                return awaitInput( sig );

        while ( 1 )
        {
                src->err = pauseThread();
                *sig = *all;

                if ( src->err )
                {
                        out->age = 0;
                        return NULL;
                }

                if ( sig->age < out->age || (sig->dst && sig->dst != src) )
                        continue;

                /* Give calling thread a chance to clean up before dying */
                if ( sig->sig == SIGNAL_TERM )
                {
                        out->age = 0;
                        return sig;
                }

                if ( val )
                {
                        if ( sig->sig == SIGNAL_CONT )
                                val = 0;
                        continue;
                }

                switch ( sig->sig )
                {
                        case SIGNAL_WAIT: val = SIGNAL_WAIT; continue;
                        case SIGNAL_EXEC:
                                if ( sig->obj.rid == out->obj.rid )
                                        val = SIGNAL_EXEC;
                                continue;
                        case SIGNAL_CONT: out->age = 0; return sig;
                }
        }

        out->age = 0;
        return sig;
}

---

If you want to look at the full source then the files to look at are:

include/basic/natives/thread.h * 6afbde92cfc3d86cc47c24fb0a79746187882e99 * Lee Shallis / Dragonbuilder * GitLab
src/basic/natives/threads.h * 6afbde92cfc3d86cc47c24fb0a79746187882e99 * Lee Shallis / Dragonbuilder * GitLab
src/basic/natives/threads.c * 6afbde92cfc3d86cc47c24fb0a79746187882e99 * Lee Shallis / Dragonbuilder * GitLab
test/basic/main.c * 6afbde92cfc3d86cc47c24fb0a79746187882e99 * Lee Shallis / Dragonbuilder * GitLab

Edit: Never mind, just found a point of error, I had passed the wrong thread object onto the thread's execution call

Managed to hit a deadlock where the age of each thread's signal is the same, been trying to come up with a way to distinguish between signals that have been process and ones that haven't, hoping someone her might have an idea outside of recording a list of all existing threads, the 2 main functions to look at are AwaitInput() & CmpSignals()

Files * bdd95a59479ff96c9b70dccfc8a39150df69ac15 * Lee Shallis / Dragonbuilder * GitLab

Doesn't matter if you need to add variables, I just want avoid mutexes and semaphores and see how the speed compares to them.

threads.c:

Code:

---

...
BASIC_EXP smax CmpSignals( const SIG *a, const SIG *b )
{
        smax one = !!a, two = !!b, cmp = one - two;

        if ( cmp )
                return cmp;

        one = (a->que == queSignals);
        two = (b->que == queSignals);
        cmp = one - two;

        if ( cmp )
                return cmp;

        one = a->src ? GetThreadRid( a->src ) : 0;
        two = b->src ? GetThreadRid( b->src ) : 0;
        cmp =  one - two;

        if ( cmp )
                return cmp;

        return CmpAges( &(a->age), &(b->age) );
}
...
BASIC_EXP SIG*        AwaitInput( ACT *src )
{
        ACT *top = TopThread();
        SIG *sig = GetCopiedSignal( src );
        SIG *out = GetOutputSignal( src );
        SIG *all = GetOutputSignal( top );
        ucap val = SIGNAL_CONT;

        if ( src == top )
        {
                memset( out, 0, sizeof(SIG) );
                return awaitInput( sig );
        }

        while ( 1 )
        {
                bool many = false;
                bool self = false;
                bool ours = false;
                out->que = QueSignal();
                src->err = pauseThread();

                if ( src->err )
                {
                        memset( out, 0, sizeof(SIG) );
                        return NULL;
                }

                /* Check if an old broadcast */
                if ( CmpSignals( all, sig ) < 0 )
                        continue;

                /* main thread needs to know we've seen the boardcast */
                *sig = *all;
                many = !(sig->dst);
                self = (!many && sig->dst == src);
                ours = (sig->obj.ptr == out->obj.ptr);

                if ( ours && !self )
                {
                        val = (val == SIGNAL_CONT) ? sig->sig : SIGNAL_CONT;
                        continue;
                }

                break;
        }

        if ( sig->sig == SIGNAL_TERM )
                SetThreadErrno( src, ECANCELED );

        memset( out, 0, sizeof(SIG) );
        return sig;
}

---

Managed to resolve the inter-thread communication problem, still needs tweaking but now I get the expected behaviour for my pseudo mutex, unlike pthread_mutex_t this doesn't need any init()/destroy() type constructors, also there's no "global" mutex that needs to be predeclared by developers, you just call ClaimShared( thread, object ) & YieldShared() whenever you want to access a resource without referencing an explicit global, not yet able to re-produce semaphores but that can come later once I've thought it through, incidentally I wound up not needing the time_t or clock_t types, however I still have a final bug to squash before I can be satisfied it's production ready for any system, here's some output to give an indication of what I mean:

Code:

---

make DEBUG=1 run
...
cd ../../bin/ && ./d-check_basic.elf
debug = 1
main_thread:  sig = 0, 'SIGNAL_NULL',  70/ 0/ 1  1: 0: 0:              0, src      0 (    0) 'kid', obj { rid = 0, nid = '(null)', def = '(null)', raw = '(null)' }
Act 63298: Hello World!
stdout now has rid 2
Spawning thread 0
main_thread:  sig = 4, 'SIGNAL_EXEC',  70/ 0/ 2  4:48:19:      557947767, src  63298 (    1) 'kid', obj { rid = 0, nid = 'PTR', def = 'void*', raw = 'void*' }
main_thread:  sig = 4, 'SIGNAL_EXEC',  70/ 0/ 2  4:48:19:      557947767, src  63297 (    0) 'top', obj { rid = 0, nid = '(null)', def = '(null)', raw = '(null)' }
Spawning thread 1
main_thread:  sig = 0, 'SIGNAL_NULL',  70/ 0/ 1  1: 0: 0:              0, src      0 (    0) 'kid', obj { rid = 0, nid = '(null)', def = '(null)', raw = '(null)' }
Spawning thread 2
main_thread:  sig = 0, 'SIGNAL_NULL',  70/ 0/ 1  1: 0: 0:              0, src      0 (    0) 'kid', obj { rid = 0, nid = '(null)', def = '(null)', raw = '(null)' }
main_thread: TestPseudoMutex(63299) claimed shared
TestPseudoMutex(63299) yielded shared
 sig = 4, 'SIGNAL_EXEC',  70/ 0/ 2  4:48:19:      558122755, src  63297 (    0) 'top', obj { rid = 2, nid = 'STDOUT', def = 'FILE*', raw = 'struct _FILE*' }
TestPseudoMutex(63301) claimed shared
TestPseudoMutex(63301) yielded shared
main_thread: TestPseudoMutex(63300) claimed shared
TestPseudoMutex(63300) yielded shared
 sig = 4, 'SIGNAL_EXEC',  70/ 0/ 2  4:48:19:      558167389, src  63300 (    4) 'kid', obj { rid = 5, nid = '(null)', def = 'THREAD', raw = 'struct _THREAD' }
make[2]: *** [makefile:30: run] Killed
...
Compilation failed.

---

I had to manually kill the app at the end there despite all but the main thread being dead. I'll add the link for the upload in a sec, just gotta grab the url

Edit: Here's the url:
Files * 74e130e1c58d262286e2877dd78634236aea4ef1 * Lee Shallis / Dragonbuilder * GitLab

For reference this is what the test code looks like:

Code:

---

#include <basic/natives.h>
#include <pthread.h>

typedef struct _ARGS {
        uint stdout_rid;
        dint argc; char **argv;
} ARGS;

time_t pseudo_mutex_start = 0;

#ifndef _DEBUG
pthread_mutex_t debug_mutex;
#endif

dint TestPseudoMutex( OBJ *obj )
{
        ACT *src = obj->src;
        ACT *top = TopThread();
        ARGS *args = GetThreadUD(top);
        OBJ o = {0};
        ucap tid = GetThreadTid(src);

        o.rid = args->stdout_rid;
        o.nid = "STDOUT";
        o.raw = "struct _FILE*";
        o.def = "FILE*";
        o.ptr = stdout;
        o.src = src;

        while ( !pseudo_mutex_start )
                PauseThread();

        /* Test our pseduo mutices */
        ClaimShared( src, &o );
        printf("TestPseudoMutex(%zu) claimed shared\n", tid );
        YieldShared( src, &o );
        printf("TestPseudoMutex(%zu) yielded shared\n", tid );
        return 0;
}

dint HelloWorld( OBJ *obj )
{
        ACT *src = obj->src;
        ACT *top = TopThread();
        ARGS *args = GetThreadUD(top);
        REF *ref = GetThreadRef(src);
        ACT *kids[3] = { NULL };
        dint i, err;
        args->stdout_rid = SpawnRid( src );

        /* We test our pseudo mutices later, at this point we just want to know
        * our threads launched */
        pthread_mutex_lock(&debug_mutex);
        printf( "Act %zu: Hello World!\n", GetThreadTid(src) );

        if ( !(args->stdout_rid) )
        {
                printf("failed to allocate rid\n");
                pthread_mutex_unlock(&debug_mutex);
                return ECANCELED;
        }

        printf("stdout now has rid %u\n", args->stdout_rid );
        pthread_mutex_unlock(&debug_mutex);

        for ( i = 0; i < 3; ++i )
        {
                pthread_mutex_lock(&debug_mutex);
                printf( "Spawning thread %d\n", i );
                pthread_mutex_unlock(&debug_mutex);
                err = SpawnThread( src, TestPseudoMutex );
                if ( err )
                        break;
                kids[i] = ref->Last;
        }

        pseudo_mutex_start = time(NULL);

        while ( i )
        {
                --i;
                AwaitThread( kids[i] );
                EraseThread( src, kids[i] );
        }

        return 0;
}

int main( int argc, char *argv[] )
{
        ARGS args = { 0, argc, argv };
        dint err;
        setbuf( stdout, NULL );
        setbuf( stderr, NULL );

#ifndef _DEBUG
        pthread_mutex_init( &debug_mutex, NULL );
#endif
        SetAllocator( TopThread(), NULL, &args );
        err = ExecThreads( HelloWorld, true );
#ifndef _DEBUG
        pthread_mutex_destroy( &debug_mutex, NULL );
#endif
        return err ? EXIT_FAILURE : EXIT_SUCCESS;
}

---

Haven't gotten round to checking the cause of the non-terminating threads but I did think of way to partition off the pseudo mutexes and pseudo semaphores, however while debugging the reliant APIs (because I knew I had to have made a mistake somewhere, fixed the few that appeared prior to this one) I encountered a segfault that I'm not sure on the cause, I'm probably overlooking something super simple given where it appears but I'm not seeing it, since my system needs to do some updates I figured I might as well post it here then kickstart those updates and hopefully someone here will spot and post the issue:

Figured out how to separate the shared data api from the thread api, now (4ac34edc) * Commits * Lee Shallis / Dragonbuilder * GitLab

src/basic/vector.c

Code:

---

...
BASIC_EXP void*        setVectorNode(        VEC *vec, uint i, void *ptr )
        { return *((void**)setBufferValue( (BUF*)vec, i, (void*)(&ptr) )); }
...

---

For anyone that wanted to help with the non-terminating thread issue I finished with the changes that partition off the pseudo mutex/semaphore api, still need to work out the pseudo semaphore part but the pseudo mutex is working without issue.

Files * 8c8734eaf28b151d4dddd5113eb39749fe4685b1 * Lee Shallis / Dragonbuilder * GitLab

Edit: Never mind, finally noticed that I had taken hold of the target threads input and sent a SIGNAL_TERM regardless of it the caller being the top thread (which deals with deleting the target thread) or being a sub thread (which releases the input after hearing the target thread has died), removing the wait for the target thread's input to be released resolved the problem.