locks

[John Skaller2]

Felix has some locks already. However there is a special case for coroutine converted to
processes. The system uses a queue local conditional spinlock. The lock is not applied
if the queue is running single threaded. The lock is used to guard system operations
such as fetching the next coroutine to run, channel I/O, etc.

These system operations also set a flag when allocating store which
prevents that allocation triggering a GC. Its basically done by:

new (gcp, shape, flag) T(args)

A side note now of import: the system allocator is protected by an OS mutex,
and in any case, malloc itself is thread safe which probably means the
user space suballocation it does is also protected by a mutex. Malloc is smart,
it also keeps thread local free lists etc I expect, so no mutex is required for
allocation using the thread local store. But it’s hard to know. In any case
the Felix allocator also has to add the allocated object to the global
GC tracking data structure (which is a JudyLArray mapping the address
of the store to the shape).

For Felix system objects, we could by pass all of this by keeping our own
thread local freelists, perhaps up to some bound: these would be allowed
to “leak” at least until the end of the program (stuff in the free lists is not
ordinarily reachable). Im not sure exactly how to do it.

I am thinking to use a spinlock for allocation instead of an OS mutex,

Anyhow this leads to the following issue: suppose I provide the user
with the specialised coroutine spinlock. By say

colock blah; ++p; end

or something.This uses the current queue’s lock so its good for wrapping
around assignments to memory shared between coroutines. If the
coroutines are running serial, then the colcok only needs to check the
flag to tell and then does nothing.

the PROBLEM with doing this is you cannot do an allocation which
would trigger a GC. Since the expression/statements are dynamic,
and can call subroutines, how are we going to set the flag to disable the GC????


If we use a *global* lock instead of a per queue lock it would be easy.
It would also support “cross thread” atomic operations (i.e. between
different coroutine schedulers). For machines iike the core i7 this would
not be a problem, but for a machine with 1024 cores the rate of contention
could be high and cause a bottleneck.

Not that spinlocks have a serious problem. They ultimately fast,
there’s no faster lock. They wait as long as necessary and no longer
PROVIDED the lock holder isn’t pre-empted and descheduled.
With a system mutex, one can expect the lock holder to be
somewhat protected from pre-emption by the OS, and the contender
probably pre-empted (what else could happen? Apart from spinning ..
the OS pretty much HAS to descheduler a lock contender.

What we would do in an embedded system is mask interrupts whilst
holding a fast spinlock, to prevent the holder being pre-empted
and leaving the conteder pointlessly spinning.


So roughly speaking spinlocks only work if the number
of threads is close to the number of CPUs in which case
pre-emptions will be rare.


—
John Skaller
ska...@internode.on.net

[John Skaller2]

~/felix>FLX_REPORT_COLLECTIONS=1 flx src/web/tut/pthread_04
…..

Thread 4 Sleep #1 for 9 sec
Thread 1 Sleep #1 for 7 sec
ZERO FOUND -- collecting!
[Gc::collect] Program requests collection
[flx_gc:gc_profile_t] actually_collect
flx_arun(80196,0x700019de6000) malloc: *** error for object 0x7f83854035a0: pointer being freed was not allocated
*** set a breakpoint in malloc_error_break to debug
Shell terminated by signal SIGABRT


Forget lldb .. its hopeless .. luckily Felix has found it wiuth FLX_DEBUG=1
Rerun:

[gc] Garbage 0x7fbae8f00b60=flx::run::async_sched[1][1/1] [#a=0,#d=0]
…
[gc] Reachable 0x7fbae9a00000=rtl::fthread_t[1][1/1] [#a=0,#d=0]
[gc] Sweeped 14
[gc] Free 0x7fbae8c037a0
[gc] Free 0x7fbae8c037f0
[gc] Free 0x7fbae8c03950
[gc] Free 0x7fbae8e00080
[gc] Free 0x7fbae8e000d0
[gc] Free 0x7fbae8f00980
[gc] Free 0x7fbae8f00b60
flx_arun(80205,0x700015183000) malloc: *** error for object 0x7fbae8f00b60: pointer being freed was not allocated


I’m not surprised. Its the async scheduler. Its a gc object. the pointer is NOT owned by any object,
rather its owned by the thread, i.e. its on the threads machine stack .. and so should be reaped
by the collector after the thread dies.

But the diagnostic is saying it was never allocated. Yet, its in the JudyLarray of allocated objects…

Hmmmm…

—
John Skaller
ska...@internode.on.net

[John Skaller2]

At present Felix scheduler lists are a C++ (doubly linked) list of pointers to fthreads,
synchronous channels have two pointers one always NULL, the other pointing to a
an slist of waiting fthreads, an slist being a pointer (in effect) to a slist_node each
with a pointer to an fthread and a next node.

I plan to eliminate both these lists entirely. Instead, I will add a “next” pointer
to the fthread object. For the scheduler, we need to push on the front and back
of the list, but only pop off the front, so we need a pointer to the first and last
fthreads. For the schannels a single pointer is enough with the low bit
set of the a list of writesr and clear for a list of readers (NULL if empty).

The effect is a DRASTIC improvement. Why? Because both context switching
no longer requires any allocations! The cost is an extra pointer in each fthread
object. But the cost is effectively negative, since all fthreads which are not
currently running are either waiting on a channel or in the scheduler queue,
so a “next” pointer is going to exist for them anyhow. So the costs is bounded
by the total number of pthreads running schedulers. So less memory, no allocations
or deallocations .. should be at least 10 times faster.

But first to find the cause of the bug reported in last email.


—
John Skaller
ska...@internode.on.net

[John Skaller2]

> [Gc::collect] Program requests collection
> [flx_gc:gc_profile_t] actually_collect
> flx_arun(80196,0x700019de6000) malloc: *** error for object 0x7f83854035a0: pointer being freed was not allocated
> *** set a breakpoint in malloc_error_break to debug
> Shell terminated by signal SIGABRT

Duh! I made async_sched garbage collected but the mainline thread still deleted it.
Fixed!

However there is another ugliness .. when spawning a pthread the client routine
is added to the scheduler queue, async object created, and the thread spawned.

The problem is, another thread might grab and start running the routine before
the thread intended to run it does, this can only happen if you have the new
processes running. But the code is ugly, instead of queuing the routine then
pulling it out of the queue it would be better to run it directly.

There is a special case: the mainline thread. What happens with that is that
the Felix driver fetches 0, 1, or 2 routines from the library the programmer said
to run. This is a shared library in dynamic mode. Felix expects a library
initialilsation routine called:

flx_start

but also allows a mainlined optionally,. called

flx_main

Flx_start has to construct the thread frame and then runs the initiialisation
code of the library, which is all the executable code written at the top
level. This is what the programmer *thinks* is the main program usually,
but it isn’t, its actually just library init code. The order of init is not fully
determinate so there is also a flx_main is you want it, this is run after
the library init if present.

So the point is the scheduler pushes flx_main then flx_start onto the scheduler
list (flx_main only if it exists .. flx_start should exist, but if it doesn’t then
the queue is just empty). Then the scheduler pulls from the list to start work.

If you spawn_pthread or spawn_process, the sequence is copied: the target
routine if first put onto the scheduler list, the thread started, then it starts
working by pulling off the list.

For spawns it would be better if the initial proc to be run was put straight
into the scheduler. I’d have to modify the mainline setup tho.


—
John Skaller
ska...@internode.on.net