Kernel upgrade

[John Skaller2]

The Felix microtasking kernel is running reasonably well in itself.
It uses spinlocks on channel I/O and the scheduler queue shared between
concurrent schedulers and performs no allocations on these functions.

However, USER code in resume() methods (and elsewhere) can cause
two dangerous operations:

1. OS mutex locks
2. OS calls in general

The first case is use of operator new to create GC objects.

The underlying malloc() pose a threat, although modern mallocs should
be using thread local store and other techniques accessing buffered
shared memory to minimise system calls. Worse though, GC allocations
require several updates to Judy tables which although efficient can still
call mallc().

Also GC collections cause huge delays if the GC is used heavily.

The Judy problem is hard. Judy actually allows you to use a different
allocator, but it is a global variable and cannot be passed to Judy functions.
Because Judy uses fixed node sizes it is perfect for a custom allocator.
Also the nodes are small and if we expect Judy to use a small fraction of the
total program allocations, it makes sense for Judy to use a specialised allocator
that does not ever return memory to the OS. Thus on a long running program,
the amortised time lost due to allocations will be zero.

Even better, temporary Judy arrys used in GC might use an arena allocator
which is simply reset to empty when the array is cleared.

However, we also need faster allocations for both system and user objects.
Ignoring the problems of coding an allocator, we want the basic operation
to be wait-free as much as possiblel that is, require either no synchronisation
by using thread local store (using Felix thread objects to hold the data NOT
system thread local storage!), or, if shared, spinlocks.

The PROBLEM is that we do have to call malloc and free to get memory.

One way around this, sort of, is to use a server thread. The server holds say
10 empty pages and the allocators call the server to request a page,
using spinlocks to do the fetch or return an unused page. Using lists
this is extremely fast.

So the problem is reduced to the server calling malloc and free,
but it is in a separate thread, so PROVIDED it maintains the
list of available pages so it is never empty when a client calls
for a page, no spinlock will be held up by memory requests.

Note spinlocks can ALWAYS be held up by pre-emptions that
de-schedule the holder of the lock, forcing the lock requestor
to spin waiting on the OS to re-scheduler the holder so it can
finish its task.

this can ONLY be avoided by assuring the computer as a whole
has all user tasks locked to a single core. Ideally, pre-emptions
would be disabled. in practice this just means finding the right
number of threads for best performance, on an 8 core that could
be 4,6,8, or even 20.

The memory server should use “machine learning” to adjust itself
so it is able to efficiently service requests. A simple algorithm could
suffice, with environment variables allowing the initial parameters to
be set.

One coding problem here: some applications want to be single threaded.
So the server will have to work in that context too, service calls will
be subroutine calls. in this case locking isn’t needed anywhere but it may
be hard to ensure locks are not used unless needed.

Presently the kernel uses a trick with the scheduler: to run coroutines
as processes (i.e. concurrently) you have to call “spawn_process”
instead of “spawn_fthread” at least once from a running coroutine.
This dynamically enables spinlocks.

Note also the algorithm for holding onto the and releasing the pthreads
used to service calls is unprincipled. i basically make all the threads
hand around until ALL threads have stopped, and, there are no async
requests.

A flexible scheme would allow a user specified allocator. in particular
the system might use a special allocator. in general, this leads to a problem
with the GC in that it now has to find the corresponding deallocator.
An obvious solution is to use yet another Judy array to track all non-standard
allocators per object.

however for bulk page allocators, we could instead check if the pointer to the
object is interior to a bulk allocated page and if so call the required deallocator,
otherwise call the standard deallocator (which calls free() at the moment).

A more constrained solution puts the allocator pointer into the type object.
When the type object (shape_t) is in the library we can statically fix the
allocator. When the flxg compiler generates the shapes, it must choose the
allocator with user guidance, statically. When the type object is created at
run time (which we don’t do at the moment) the allocator can be passed
to the constructor.

But this method fixes the allocator based on the type of the object.

The best solution is probably to do BOTH. in other words, we maintain
a Judy array for “per object exceptions” to the allocator specified
in the type object.

We note this slows down all deallocations, whilst the overhead of
recording a special allocation is acceptable because .. well .. its
special.

So .. there’s some work to consider. At present I want to write a
hard specification for the kernel: data structures and API.

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

[John Skaller2]

Strings
======

I have added the notation:

s . i

for s a string and i an int. Previously, and surprisingly, this didn’t work,
you had to use s.[i] which I consider deprecated now, along with

s.[i to j]

etc since we have slices now (and they actually do work)


Arrays
=====

Felix has three important kinds of arrays:

* Arrays
* carray[T] aka +T
* varray[T]

Now, with actual array, which are passed by value, we have two projections,
value projections and pointer projections:

var x : int ^ 10;
&x . 1 <- x . 2;

which allow assignments and extractions with only the storeat procediure <-
The arguments are both purely functional.

But for C and V arrays, nope. The problem is both are already pointers
underneath. Since

a . i

means to get the i’th component from the array, it can’t also mean to
get a pointer to the i’th component. But technically this is just wrong
because a . i should be a pointer, since a is a pointer already, at least
underneath. But we cannot use

&a . i

for the pointer case because the address of a value of any kind is not
allowed, addressing is NOT an operator, its just a way to spell the
address of a variable. It doesn’t make sense to take the address
of a pointer because it is already an address.

Now a carray is actually an incrementable pointer:

a + i

is in fact allowed. This code works:

var a : +int = array_alloc[int] 10;
for var i in 0 upto 9 do
set(a, i, i * i);
set(a,i,get(a,i)+1);
done
for i in 0 upto 9 do
println$ a.[i], *(a+i), a.i;
done
var p = a;
while p != a + 10 do
println$ *p;
++p;
done
free a;

So, a carray pointer behaves just like a C pointer EXCEPT we use

p . i

instead of p[i]. Note p.[i] works too but as for strings will be deprecated.
Note in particular:

p + 1

is exactly as in C. As is

*p

but only for values. To assign to a C array we MUST use

set (p, i, v)

note the second argument should NOT be needed, since this should work
and is more consistent:

set (p + i, v);

which suggests this should work too;

p + i <- v;

Hmmm.

OK so both done! Summary:

NEW NOTATION for C arrays. (Shoud be applied to varray too!):

p <- v;

stores v at pointer p, where p is a carray.

Note this means that in:

p + i

the + i is acting like a pointer projection. Whereas in

p . i

it’s a value projection.



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

[John Skaller2]

Felix now does this (the diagnostics will be removed):

~/felix>flx hello
AFTER PROCESSING COMMAND LINE SWITCHES, prepend user package dir to flx_pkgconfig search path
HOME: Felix home dir is /Users/skaller/.felix
BASE: Felix package manager config directories are list('/Users/skaller/felix/build/release/host/config')
TARGET: Felix target subdir
UPDATED: Felix package manager config directories are list('/Users/skaller/.felix/host/config', '/Users/skaller/felix/build/release/host/config')
Hello World


If the —target is not specified, it is taken as “host”.
Then when flx_pkgconfig (built in to flx) searches for packages it first looks
in

FLX_HOME_DIR/ target/config

where target is the specified target or host if omitted. Note there is an option
to specify the target directory in full, if you do this, “host” is used as the target.

This allows custom additions and overrides, per target, to be added to your
home directory felix config so as to modify the standard or installed
package meta-data, or add new packages, in a way that is not impacted
by a full Felix rebuild.


Note that *.fpc files in FLX_HOME_DIR/config are NOT searched.
They are, however, installed in build/release/host/config when doing
a full rebuild from scratch (i.e. using Python encoded fbuild bootstrap).





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

[John Skaller2]

Felix now has partially hacky support for Objective C. This now works:

/////////////////////////
@implementation SmallClass
- (instancetype)init {
self = [super init];
return self;
}
- (int)get1977 {
return 1977;
}
@end
""";

type small_class_instance_t = "void*" requires
small_class_interface,
small_class_implementation,
package "objc"
;

fun make_small_class_instance:
1 -> small_class_instance_t
=
"[[SmallClass alloc] init]"
;

fun get1977 : small_class_instance_t -> int = "[$1 get1977]";

var small_class_instance = make_small_class_instance();
var result = get1977 small_class_instance;
println$ "Felix ran objc to get " + result.str;
//////////////////////

It only works on MacOSX with because I only provided the package for that platform.
It may only work with clang, not sure.

Note the package will be installed automatically ONLY on a bootstrap build.
[I thought i wrote a tool to do this but can’t find it.]

Otherwise you need to make rebuild after git pull and then do

cp src/config/macosx/objc.fpc build/release/host/config/

NOTE: you have to use c”…” to prevent @ substitution.
If you want substitution with @, you have to use @@ to emit @.


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

[John Skaller2]

So a very simple way to enhance Felix ObjC interfacing capability is to forget about
making it type safe .. since ObjC isn’t in the first place.

Consider the cases

[obj meth]
[obj meth:arg]
[obj meth:arg1 tag2:arg2]
[obj meth:arg1 tag2:arg2 tag3:arg3]

The tag order matters. In Felix the first call would be said to take a unit argument.

Now if we had a syntax like:

@@[…]

as above, Felix could just translate this to

[OBJ meth: ARG1 tag2: ARG2 tag3:ARG3]

where obj, arg1, arg2 are FELIX expressions and OBJ ARG1 ARG2
are the C code that Felix would emit for them already.

This requires a small change to the parser only, HOWEVER
the compiler will need a new construction.

In fact this is very close to a struct:

struct meth { meth: arg1_type; tag2: arg2_type; tag3: arg3_type; }

but structs would have to be defined before use. Records don’t have to be
however the order of the fields in a record is undefined and the actual
implementation sorts them alphabetically.

So one way or the other, I don’t think this can be done without a compiler change.

Note: the idea is Felix only needs to know NSObject type.
NO BINDINGS ARE REQUIRED.

The code will always compile (fi the Felix argument expressions do of course).
It will also always run. It may give an error if the object doesn’t know the method,
but that’s Objective C standard behaviour.

Note doing this DOES NOT EXCLUDE also writing type safe bindings.


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

[John Skaller2]

> On 18 Aug 2020, at 21:04, John Skaller2 <ska...@internode.on.net> wrote:
>
> So a very simple way to enhance Felix ObjC interfacing capability is to forget about
> making it type safe .. since ObjC isn’t in the first place.
>
> Consider the cases
>
> [obj meth]
> [obj meth:arg]
> [obj meth:arg1 tag2:arg2]
> [obj meth:arg1 tag2:arg2 tag3:arg3]
>
> The tag order matters. In Felix the first call would be said to take a unit argument.
>
> Now if we had a syntax like:
>
> @@[…]
>
> as above, Felix could just translate this to
>
> [OBJ meth: ARG1 tag2: ARG2 tag3:ARG3]
>
> where obj, arg1, arg2 are FELIX expressions and OBJ ARG1 ARG2
> are the C code that Felix would emit for them already.
>
> This requires a small change to the parser only, HOWEVER
> the compiler will need a new construction.
>
> In fact this is very close to a struct:
>
> struct meth { meth: arg1_type; tag2: arg2_type; tag3: arg3_type; }
>
> but structs would have to be defined before use. Records don’t have to be
> however the order of the fields in a record is undefined and the actual
> implementation sorts them alphabetically.

So there seem to be two options:

(a) some kind of anonymous struct type
(b) just a way to do a message send

Option (a) has the advantage that you could store a message in a variable,
and then send it to some object later. But it is a lot of work and there are
issues with the type.

The problem is that anon struct would be identifier by:

1. The method name is the struct name
2. The first argument type (possibly unit)
3. A list of name type pairs.

Since it’s a structural type, two types would only be equal
if all the above 1,2,3 were. The problem is with the subtyping
required in Objective C, a value of type NSString for one component
in one value, and of type NSObject for the same component would mean
the types are not equal. The only realistic way two values would be equal
would be (a) accidental construction of the same type and (b) copying.

The matching rules used to decide for example if a value cam be passed
as an argument to a function, however, are simple and similar to those
used for records: if the parameter type is an anonymous struct type,
then the same rules apply: the arguments can be subtypes for matching
field names, and some fields could be omitted: both depth and width
subtyping.

In addition, we could allow these things to be passed where
named parameters act like tags and where the function is taking
a record type, in a way similar to what works right now with
records.

This much better than the disaster in Swift where each function
parameter has TWO names: the parameter name AND a tag name.
What a complete mess Swift has become trying to get ObjC compat
the wrong way by giving functions multiple arguments!!!!

On the other hand a plain message send syntax avoids all these
complications and can be done with minimal compiler changes
and without introducing any new types. however this means
you cannot store a message in a variable and then send it
later, nor copy it.

In ObjC if I understand right ANY message can be sent to
ANY object. It may fail at compile time if the object type
is not compatible with the receiver type of the send operation.
Otherwise it fails at run time. Felix can ignore both these
issues and allow anything, and just let the ObjC compiler
bug out if the typing is statically incorrect.

In fact that can be avoided by casting EVERYTHING with
an ObjC flavour to NSObject so the only static compile time
type errors would be using a non-ObjC type somewhere.
Even better with subtyping, a Felix string, for example,
could automatically convert to a NSString. And NSString
converts to NSObject if necessary.

These two methods may or may not be exclusive.
i suspect not exclusive. i’m inclined to do the second method,
the easy one. I note that I think ObjC does have facilities to wrap
message into single objects so the feature provided by the first
method is probably available anyhow.

I note also that I have not done @{..} for dictionaries yet.
Also you can send messages right now with C bindings:

fun make_small_class_instance:
1 -> small_class_instance_t
=
"[[SmallClass alloc] init]"
;

and of course this includes parameter passing. This would be

let SmallClass = .. in
@@[ @@[SmallClass alloc] init]

in my proposed notation. Note that “alloc” and “init” here
are magic identifiers not values, but SmallClass is a value.
This requires some tricky parsing.


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

[John Skaller2]

Arrgh. Nope. There’s no easy way to propagate the info to the back end.

Also major problem and an absolute killer design fault in Objective C:
the return type. Felix needs it specified or fixed at NSObject, but that
will not work in the test case which returns int.

Hmm. WTF does ObjC do if a method returns int, but you cast the object
to NSObject and send it the message? The only possible return type
is NSObject. [Well “id” actually I suppose, but “int” certainly isn’t that]



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

[John Skaller2]

Ok so this can ALREADY do it:


//$ Embed a C statement into Felix code with arguments.
private cbind_stmt:= "cstmt" scode_spec sexpr? ";" =># "`(ast_code ,_sr ,_2 ,_3)";


//$ Embed a C statement which does not return normally
//$ into Felix code. For example:
//$
//$ noreturn cstmt "exit(0);";
//$
private cbind_stmt:= "noreturn" "cstmt" scode_spec sexpr? ";" =># "`(ast_noreturn_code ,_sr ,_3 ,_4)";

//$ Embed a C expression into Felix.
//$ This required giving the Felix type of the expression.
//$ The expression is contained in the string. For example:
//$
//$ cexpr [double] "sin(0.7)” endcexpr
//$
satom := "cexpr" "[" stypeexpr "]" scode_spec sexpr? "endcexpr" =># "`(ast_expr ,_sr ,_5 ,_3 ,_6)";

//$ A short form embedding for variables.
//$
//$ code [double] M_PI
//$
satom := "cvar" "[" stypeexpr "]" sname =># "`(ast_expr ,_sr (Str ,_5) ,_3 ())”;

So for a method call that doesn’t return an interesting value, with no arguments:

cstmt [obj method];
cstmt “[$1 method]” obj;

with an argument:

cstmt “[$1 method:$2]” (obj, arg);

For a method that does return a value of type T with no arguments:

cexpr [T] “[$1 method]” obj endcexpr

and with one argument:

cexpr [T] [$1 method:$2]” (obj, arg) endcexpr

The only difference to ObjC syntax apart from using keywords instead of say @@[..] is
that for expressions you have to specify the type. Note we even have closures:

fun (x:int) => cexpr [double] “(double)($1)” x endcexpr

which has type int -> double.

“cexpr” .. “endcexpr” is a bit long winded but @@[..] can’t work without specifying
the type being returned. We don’t care about the argument types, ObjC compiler will
do the barfing for us.


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