This is more question of implementating high-level languages,
but possible answers depend on computer architecture.

Problem: We want to code in high-level language and we want
to respond to asynchronous events. Simplest example may
by timeout (response to timer interrupt). Or we may wish
to change what the program is doing in response to external
event. At hardware level there are interrupt, at operating
system level we may get signals, so no problem at low level.
However, high-level language may have data structures with
non-trivial invariants. If we abort modification in the
middle data structures may be left in inconsistent state.
So, what is needed is transfer of control to handler at
next safepoint, that is at next place where program may be
safely interrupted. I assume that high-level language
compiler knows where safepoints are, so the only problem
is how to perform control transfer from safepoint to
handler. This is essentially what (in)famous "came from"
instruction is doing, but I am not aware of any real
hardware implementing "came from"...

Possible solutions:

1) Set a flag in signal handler and check for the flag at
each safepoint. Low-level variant od this would keep
interrupts disabled most of the time and enable them
only at safepoints. This is problematic, because
checking inside tight loop may lead to significant
performance drop. Not checking inside loop may
lead to long delay before reaction to external signal.
Inserting checking code by hand could work, but is
error-prone and labor-intensive, so I want automatic
solution, that is compiler generated checks.
2) Using debug registers: debug register causes transfer
to handler after arriving at designated address. This
is quite close to what "came from" should do and would
be a satisfactory solution. Unfortunately, debug
registers are not standard part of architecture and
access to debug registers may be restricted by operating
system.
3) Separate cleanup routines: each instruction would have
associated cleanup routine which will continue computations
up to safepoint, but then transfer control to handler.
This may be quite satisfactory from performance point
of view, but require quite a lot of code.
4) Modyfing code to replace instruction at safepoint
by jump. This has usual disadvantages of self-modyfying
code, but otherwise looks reasonable.
5) Dynamicaly generating cleanup code: we could copy code
from current instruction pointer up to setpoint and add
jump to handler at the end. Assuming that code is position
independent this should work and is resonably simple. We
avoid modification of "normal code", but it is not clear
for me if modern CPU-s like it better than 4.
6) Interpret machine instructions up to safepoint. Shuld work,
but is lot of code and potentialy slow.
7) Modification of 3 and 6: generate cleanups as bytecode and
interpret it. IIUC this is essentially what DWARF is doing
to handle C++ exceptions. My impression is that this is
complicated to implement, requires a lot of code space and
is slow a runtime. OTOH less complicated than 6, probably
runs faster than 6 and needs less code space than 3.

I wonder if there is other possible implementation that I
overlooked? And advantages/disadvantages that I overlooked?

--
Waldek Hebisch

On Friday, July 30, 2021 at 4:47:22 PM UTC-5, anti...@math.uni.wroc.pl wrote:
> This is more question of implementating high-level languages,
> but possible answers depend on computer architecture.
>
> Problem: We want to code in high-level language and we want
> to respond to asynchronous events. Simplest example may
> by timeout (response to timer interrupt). Or we may wish
> to change what the program is doing in response to external
> event. At hardware level there are interrupt, at operating
> system level we may get signals, so no problem at low level.
> However, high-level language may have data structures with
> non-trivial invariants. If we abort modification in the
> middle data structures may be left in inconsistent state.
<
I might interject at this instant, that My 66000 has this kind of
behavior with its ATOMIC events (multiple word ATOMICs.)
If the ATOMIC event fails to complete, control is transferred
to a place where SW understands that it is no longer "IN" the
ATOMIC event. Exceptions and interrupts terminate the
ATOMIC event and perform said transfer of control, there are
branch instructions which can conditionally transfer control
out of the ATOMIC event and thus terminate it uncessfully.
<
One of the reason I inverted it was so that a concurrent data
structure could have an element moved from one location in
the CDS to another location without every being detected as
"NOT IN" the CDS. Normal ATOMIC events (such as Compare
double swap double) cannot perform this. This improves the
invariants while reducing the number of ATOMIC events.
<
What I don't understand about OP's statement is when we might
need such an invariant manifest when we are not also doing some-
thing that needs to smell ATOMIC. Can OP expand on this ?
<
> So, what is needed is transfer of control to handler at
> next safepoint, that is at next place where program may be
> safely interrupted.
<
An interrupt, be definition, is asynchronous to the program.
Indeed, it is foreign to the program, the program should know
nothing about it except that it happened and control has
returned.
<
Does OP really mean interrupt, here ?
<
Could OP mean exception instead ?
<
> I assume that high-level language
> compiler knows where safepoints are, so the only problem
> is how to perform control transfer from safepoint to
> handler. This is essentially what (in)famous "came from"
> instruction is doing, but I am not aware of any real
> hardware implementing "came from"...
>
> Possible solutions:
<
From above to establish context::
> Problem: We want to code in high-level language and we want
> to respond to asynchronous events. Simplest example may
> by timeout (response to timer interrupt). Or we may wish
> to change what the program is doing in response to external
> event.
<
Why not have the asynchronous event create a worklist and when
the program gets around to checking for new elements on the
asynchronous work list, it devotes some resources to making that
work happen. Thus, the only thing the asynchronous handler would
be doing is to lob units of work on said worklist (probably ATOMICally.)
<
This is basically what interrupt handlers do today--the lob work onto
the worklist and dismiss the interrupt. then they schedule the OS
which looks at the worklist (job queue) which then context switches
into the real handler, and performs a unit or work; then it all unwinds
so control eventually returns to interrupted program.
>
> 1) Set a flag in signal handler and check for the flag at
> each safepoint. Low-level variant od this would keep
> interrupts disabled most of the time and enable them
> only at safepoints. This is problematic, because
> checking inside tight loop may lead to significant
> performance drop. Not checking inside loop may
> lead to long delay before reaction to external signal.
> Inserting checking code by hand could work, but is
> error-prone and labor-intensive, so I want automatic
> solution, that is compiler generated checks.
> 2) Using debug registers: debug register causes transfer
> to handler after arriving at designated address. This
> is quite close to what "came from" should do and would
> be a satisfactory solution. Unfortunately, debug
> registers are not standard part of architecture and
> access to debug registers may be restricted by operating
> system.
> 3) Separate cleanup routines: each instruction would have
> associated cleanup routine which will continue computations
> up to safepoint, but then transfer control to handler.
> This may be quite satisfactory from performance point
> of view, but require quite a lot of code.
> 4) Modyfing code to replace instruction at safepoint
> by jump. This has usual disadvantages of self-modyfying
> code, but otherwise looks reasonable.
> 5) Dynamicaly generating cleanup code: we could copy code
> from current instruction pointer up to setpoint and add
> jump to handler at the end. Assuming that code is position
> independent this should work and is resonably simple. We
> avoid modification of "normal code", but it is not clear
> for me if modern CPU-s like it better than 4.
> 6) Interpret machine instructions up to safepoint. Shuld work,
> but is lot of code and potentialy slow.
> 7) Modification of 3 and 6: generate cleanups as bytecode and
> interpret it. IIUC this is essentially what DWARF is doing
> to handle C++ exceptions. My impression is that this is
> complicated to implement, requires a lot of code space and
> is slow a runtime. OTOH less complicated than 6, probably
> runs faster than 6 and needs less code space than 3.
>
> I wonder if there is other possible implementation that I
> overlooked? And advantages/disadvantages that I overlooked?
<
2 level interrupt handling:
<
First level creates a unit of work on the job queue and dismisses interrupt.
If work was put on job queue, then invoke OS scheduler, otherwise return
from interrupt. This level has to be short and fast doing as little as possible
to keep interrupt responsiveness high.
<
Second level takes unit of work off job queue and processes the unit of work.
When job queue is empty, return control back to interrupted program. This
level only has to methodologically work thought the job queue.
<
We have been doing it this way for at least 6 decades.
>
> --
> Waldek Hebisch

On 7/30/2021 2:47 PM, antispam@math.uni.wroc.pl wrote:
> This is more question of implementating high-level languages,
> but possible answers depend on computer architecture.
>
> Problem: We want to code in high-level language and we want
> to respond to asynchronous events. Simplest example may
> by timeout (response to timer interrupt). Or we may wish
> to change what the program is doing in response to external
> event. At hardware level there are interrupt, at operating
> system level we may get signals, so no problem at low level.
> However, high-level language may have data structures with
> non-trivial invariants. If we abort modification in the
> middle data structures may be left in inconsistent state.
> So, what is needed is transfer of control to handler at
> next safepoint, that is at next place where program may be
> safely interrupted. I assume that high-level language
> compiler knows where safepoints are, so the only problem
> is how to perform control transfer from safepoint to
> handler. This is essentially what (in)famous "came from"
> instruction is doing, but I am not aware of any real
> hardware implementing "came from"...
>
> Possible solutions:
>
> 1) Set a flag in signal handler and check for the flag at
> each safepoint. Low-level variant od this would keep
> interrupts disabled most of the time and enable them
> only at safepoints. This is problematic, because
> checking inside tight loop may lead to significant
> performance drop. Not checking inside loop may
> lead to long delay before reaction to external signal.
> Inserting checking code by hand could work, but is
> error-prone and labor-intensive, so I want automatic
> solution, that is compiler generated checks.
> 2) Using debug registers: debug register causes transfer
> to handler after arriving at designated address. This
> is quite close to what "came from" should do and would
> be a satisfactory solution. Unfortunately, debug
> registers are not standard part of architecture and
> access to debug registers may be restricted by operating
> system.
> 3) Separate cleanup routines: each instruction would have
> associated cleanup routine which will continue computations
> up to safepoint, but then transfer control to handler.
> This may be quite satisfactory from performance point
> of view, but require quite a lot of code.
> 4) Modyfing code to replace instruction at safepoint
> by jump. This has usual disadvantages of self-modyfying
> code, but otherwise looks reasonable.
> 5) Dynamicaly generating cleanup code: we could copy code
> from current instruction pointer up to setpoint and add
> jump to handler at the end. Assuming that code is position
> independent this should work and is resonably simple. We
> avoid modification of "normal code", but it is not clear
> for me if modern CPU-s like it better than 4.
> 6) Interpret machine instructions up to safepoint. Shuld work,
> but is lot of code and potentialy slow.
> 7) Modification of 3 and 6: generate cleanups as bytecode and
> interpret it. IIUC this is essentially what DWARF is doing
> to handle C++ exceptions. My impression is that this is
> complicated to implement, requires a lot of code space and
> is slow a runtime. OTOH less complicated than 6, probably
> runs faster than 6 and needs less code space than 3.
>
> I wonder if there is other possible implementation that I
> overlooked? And advantages/disadvantages that I overlooked?
>

Simplest to implement would be to throw a C++ exception in the signal
handler and catch at the safepoint (catches are always safepoints in
C++). That lets C++ do the dwarfing instead of you.

On 2021-07-30, antispam@math.uni.wroc.pl <antispam@math.uni.wroc.pl> wrote:
> This is more question of implementating high-level languages,
> but possible answers depend on computer architecture.
>
> Problem: We want to code in high-level language and we want
> to respond to asynchronous events. Simplest example may
> by timeout (response to timer interrupt). Or we may wish
> to change what the program is doing in response to external
> event. At hardware level there are interrupt, at operating
> system level we may get signals, so no problem at low level.
> However, high-level language may have data structures with
> non-trivial invariants. If we abort modification in the
> middle data structures may be left in inconsistent state.
> So, what is needed is transfer of control to handler at
> next safepoint, that is at next place where program may be
> safely interrupted. I assume that high-level language
> compiler knows where safepoints are, so the only problem
> is how to perform control transfer from safepoint to
> handler. This is essentially what (in)famous "came from"
> instruction is doing, but I am not aware of any real
> hardware implementing "came from"...
>
> Possible solutions:
>
> 1) Set a flag in signal handler and check for the flag at
> each safepoint. Low-level variant od this would keep
> interrupts disabled most of the time and enable them
> only at safepoints. This is problematic, because
> checking inside tight loop may lead to significant
> performance drop. Not checking inside loop may
> lead to long delay before reaction to external signal.
> Inserting checking code by hand could work, but is
> error-prone and labor-intensive, so I want automatic
> solution, that is compiler generated checks.
> 2) Using debug registers: debug register causes transfer
> to handler after arriving at designated address. This
> is quite close to what "came from" should do and would
> be a satisfactory solution. Unfortunately, debug
> registers are not standard part of architecture and
> access to debug registers may be restricted by operating
> system.
> 3) Separate cleanup routines: each instruction would have
> associated cleanup routine which will continue computations
> up to safepoint, but then transfer control to handler.
> This may be quite satisfactory from performance point
> of view, but require quite a lot of code.
> 4) Modyfing code to replace instruction at safepoint
> by jump. This has usual disadvantages of self-modyfying
> code, but otherwise looks reasonable.
> 5) Dynamicaly generating cleanup code: we could copy code
> from current instruction pointer up to setpoint and add
> jump to handler at the end. Assuming that code is position
> independent this should work and is resonably simple. We
> avoid modification of "normal code", but it is not clear
> for me if modern CPU-s like it better than 4.
> 6) Interpret machine instructions up to safepoint. Shuld work,
> but is lot of code and potentialy slow.
> 7) Modification of 3 and 6: generate cleanups as bytecode and
> interpret it. IIUC this is essentially what DWARF is doing
> to handle C++ exceptions. My impression is that this is
> complicated to implement, requires a lot of code space and
> is slow a runtime. OTOH less complicated than 6, probably
> runs faster than 6 and needs less code space than 3.
>
> I wonder if there is other possible implementation that I
> overlooked? And advantages/disadvantages that I overlooked?
>
Signals are obsolete long ago. Now use threads and implement
user space scheduler.

--
bmaxa now listens Yammat FM

Ivan Godard <ivan@millcomputing.com> wrote:
> On 7/30/2021 2:47 PM, antispam@math.uni.wroc.pl wrote:
> > This is more question of implementating high-level languages,
> > but possible answers depend on computer architecture.
> >
> > Problem: We want to code in high-level language and we want
> > to respond to asynchronous events. Simplest example may
> > by timeout (response to timer interrupt). Or we may wish
> > to change what the program is doing in response to external
> > event. At hardware level there are interrupt, at operating
> > system level we may get signals, so no problem at low level.
> > However, high-level language may have data structures with
> > non-trivial invariants. If we abort modification in the
> > middle data structures may be left in inconsistent state.
> > So, what is needed is transfer of control to handler at
> > next safepoint, that is at next place where program may be
> > safely interrupted. I assume that high-level language
> > compiler knows where safepoints are, so the only problem
> > is how to perform control transfer from safepoint to
> > handler. This is essentially what (in)famous "came from"
> > instruction is doing, but I am not aware of any real
> > hardware implementing "came from"...
> >
> > Possible solutions:
> >
> > 1) Set a flag in signal handler and check for the flag at
> > each safepoint. Low-level variant od this would keep
> > interrupts disabled most of the time and enable them
> > only at safepoints. This is problematic, because
> > checking inside tight loop may lead to significant
> > performance drop. Not checking inside loop may
> > lead to long delay before reaction to external signal.
> > Inserting checking code by hand could work, but is
> > error-prone and labor-intensive, so I want automatic
> > solution, that is compiler generated checks.
> > 2) Using debug registers: debug register causes transfer
> > to handler after arriving at designated address. This
> > is quite close to what "came from" should do and would
> > be a satisfactory solution. Unfortunately, debug
> > registers are not standard part of architecture and
> > access to debug registers may be restricted by operating
> > system.
> > 3) Separate cleanup routines: each instruction would have
> > associated cleanup routine which will continue computations
> > up to safepoint, but then transfer control to handler.
> > This may be quite satisfactory from performance point
> > of view, but require quite a lot of code.
> > 4) Modyfing code to replace instruction at safepoint
> > by jump. This has usual disadvantages of self-modyfying
> > code, but otherwise looks reasonable.
> > 5) Dynamicaly generating cleanup code: we could copy code
> > from current instruction pointer up to setpoint and add
> > jump to handler at the end. Assuming that code is position
> > independent this should work and is resonably simple. We
> > avoid modification of "normal code", but it is not clear
> > for me if modern CPU-s like it better than 4.
> > 6) Interpret machine instructions up to safepoint. Shuld work,
> > but is lot of code and potentialy slow.
> > 7) Modification of 3 and 6: generate cleanups as bytecode and
> > interpret it. IIUC this is essentially what DWARF is doing
> > to handle C++ exceptions. My impression is that this is
> > complicated to implement, requires a lot of code space and
> > is slow a runtime. OTOH less complicated than 6, probably
> > runs faster than 6 and needs less code space than 3.
> >
> > I wonder if there is other possible implementation that I
> > overlooked? And advantages/disadvantages that I overlooked?
> >
>
> Simplest to implement would be to throw a C++ exception in the signal
> handler and catch at the safepoint (catches are always safepoints in
> C++). That lets C++ do the dwarfing instead of you.

Sorry, wont do. One problem is that I have native code compiler
with precise garbage collector. In C++ I would have to use
interpreter. There would be substantial slowdown. And going with
interpreter (not necesserly in C) implementing safepoints
is not a problem, except for performance hit...

--
Waldek Hebisch

On 2021-07-31, antispam@math.uni.wroc.pl <antispam@math.uni.wroc.pl> wrote:
> Ivan Godard <ivan@millcomputing.com> wrote:
>> On 7/30/2021 2:47 PM, antispam@math.uni.wroc.pl wrote:
>> > This is more question of implementating high-level languages,
>> > but possible answers depend on computer architecture.
>> >
>> > Problem: We want to code in high-level language and we want
>> > to respond to asynchronous events. Simplest example may
>> > by timeout (response to timer interrupt). Or we may wish
>> > to change what the program is doing in response to external
>> > event. At hardware level there are interrupt, at operating
>> > system level we may get signals, so no problem at low level.
>> > However, high-level language may have data structures with
>> > non-trivial invariants. If we abort modification in the
>> > middle data structures may be left in inconsistent state.
>> > So, what is needed is transfer of control to handler at
>> > next safepoint, that is at next place where program may be
>> > safely interrupted. I assume that high-level language
>> > compiler knows where safepoints are, so the only problem
>> > is how to perform control transfer from safepoint to
>> > handler. This is essentially what (in)famous "came from"
>> > instruction is doing, but I am not aware of any real
>> > hardware implementing "came from"...
>> >
>> > Possible solutions:
>> >
>> > 1) Set a flag in signal handler and check for the flag at
>> > each safepoint. Low-level variant od this would keep
>> > interrupts disabled most of the time and enable them
>> > only at safepoints. This is problematic, because
>> > checking inside tight loop may lead to significant
>> > performance drop. Not checking inside loop may
>> > lead to long delay before reaction to external signal.
>> > Inserting checking code by hand could work, but is
>> > error-prone and labor-intensive, so I want automatic
>> > solution, that is compiler generated checks.
>> > 2) Using debug registers: debug register causes transfer
>> > to handler after arriving at designated address. This
>> > is quite close to what "came from" should do and would
>> > be a satisfactory solution. Unfortunately, debug
>> > registers are not standard part of architecture and
>> > access to debug registers may be restricted by operating
>> > system.
>> > 3) Separate cleanup routines: each instruction would have
>> > associated cleanup routine which will continue computations
>> > up to safepoint, but then transfer control to handler.
>> > This may be quite satisfactory from performance point
>> > of view, but require quite a lot of code.
>> > 4) Modyfing code to replace instruction at safepoint
>> > by jump. This has usual disadvantages of self-modyfying
>> > code, but otherwise looks reasonable.
>> > 5) Dynamicaly generating cleanup code: we could copy code
>> > from current instruction pointer up to setpoint and add
>> > jump to handler at the end. Assuming that code is position
>> > independent this should work and is resonably simple. We
>> > avoid modification of "normal code", but it is not clear
>> > for me if modern CPU-s like it better than 4.
>> > 6) Interpret machine instructions up to safepoint. Shuld work,
>> > but is lot of code and potentialy slow.
>> > 7) Modification of 3 and 6: generate cleanups as bytecode and
>> > interpret it. IIUC this is essentially what DWARF is doing
>> > to handle C++ exceptions. My impression is that this is
>> > complicated to implement, requires a lot of code space and
>> > is slow a runtime. OTOH less complicated than 6, probably
>> > runs faster than 6 and needs less code space than 3.
>> >
>> > I wonder if there is other possible implementation that I
>> > overlooked? And advantages/disadvantages that I overlooked?
>> >
>>
>> Simplest to implement would be to throw a C++ exception in the signal
>> handler and catch at the safepoint (catches are always safepoints in
>> C++). That lets C++ do the dwarfing instead of you.
>
> Sorry, wont do. One problem is that I have native code compiler
> with precise garbage collector. In C++ I would have to use
> interpreter. There would be substantial slowdown. And going with
> interpreter (not necesserly in C) implementing safepoints
> is not a problem, except for performance hit...

Good luck with that :P
>

--
bmaxa now listens Yammat FM

On 2021-07-30, Ivan Godard <ivan@millcomputing.com> wrote:
> On 7/30/2021 2:47 PM, antispam@math.uni.wroc.pl wrote:
>> This is more question of implementating high-level languages,
>> but possible answers depend on computer architecture.
>>
>> Problem: We want to code in high-level language and we want
>> to respond to asynchronous events. Simplest example may
>> by timeout (response to timer interrupt). Or we may wish
>> to change what the program is doing in response to external
>> event. At hardware level there are interrupt, at operating
>> system level we may get signals, so no problem at low level.
>> However, high-level language may have data structures with
>> non-trivial invariants. If we abort modification in the
>> middle data structures may be left in inconsistent state.
>> So, what is needed is transfer of control to handler at
>> next safepoint, that is at next place where program may be
>> safely interrupted. I assume that high-level language
>> compiler knows where safepoints are, so the only problem
>> is how to perform control transfer from safepoint to
>> handler. This is essentially what (in)famous "came from"
>> instruction is doing, but I am not aware of any real
>> hardware implementing "came from"...
>>
>> Possible solutions:
>>
>> 1) Set a flag in signal handler and check for the flag at
>> each safepoint. Low-level variant od this would keep
>> interrupts disabled most of the time and enable them
>> only at safepoints. This is problematic, because
>> checking inside tight loop may lead to significant
>> performance drop. Not checking inside loop may
>> lead to long delay before reaction to external signal.
>> Inserting checking code by hand could work, but is
>> error-prone and labor-intensive, so I want automatic
>> solution, that is compiler generated checks.
>> 2) Using debug registers: debug register causes transfer
>> to handler after arriving at designated address. This
>> is quite close to what "came from" should do and would
>> be a satisfactory solution. Unfortunately, debug
>> registers are not standard part of architecture and
>> access to debug registers may be restricted by operating
>> system.
>> 3) Separate cleanup routines: each instruction would have
>> associated cleanup routine which will continue computations
>> up to safepoint, but then transfer control to handler.
>> This may be quite satisfactory from performance point
>> of view, but require quite a lot of code.
>> 4) Modyfing code to replace instruction at safepoint
>> by jump. This has usual disadvantages of self-modyfying
>> code, but otherwise looks reasonable.
>> 5) Dynamicaly generating cleanup code: we could copy code
>> from current instruction pointer up to setpoint and add
>> jump to handler at the end. Assuming that code is position
>> independent this should work and is resonably simple. We
>> avoid modification of "normal code", but it is not clear
>> for me if modern CPU-s like it better than 4.
>> 6) Interpret machine instructions up to safepoint. Shuld work,
>> but is lot of code and potentialy slow.
>> 7) Modification of 3 and 6: generate cleanups as bytecode and
>> interpret it. IIUC this is essentially what DWARF is doing
>> to handle C++ exceptions. My impression is that this is
>> complicated to implement, requires a lot of code space and
>> is slow a runtime. OTOH less complicated than 6, probably
>> runs faster than 6 and needs less code space than 3.
>>
>> I wonder if there is other possible implementation that I
>> overlooked? And advantages/disadvantages that I overlooked?
>>
>
> Simplest to implement would be to throw a C++ exception in the signal
> handler and catch at the safepoint (catches are always safepoints in
> C++). That lets C++ do the dwarfing instead of you.
In signal handler you can't call printf let alone throw C++ exception :P

--
bmaxa now listens Yammat FM

MitchAlsup <MitchAlsup@aol.com> wrote:
> On Friday, July 30, 2021 at 4:47:22 PM UTC-5, anti...@math.uni.wroc.pl wrote:
> > This is more question of implementating high-level languages,
> > but possible answers depend on computer architecture.
> >
> > Problem: We want to code in high-level language and we want
> > to respond to asynchronous events. Simplest example may
> > by timeout (response to timer interrupt). Or we may wish
> > to change what the program is doing in response to external
> > event. At hardware level there are interrupt, at operating
> > system level we may get signals, so no problem at low level.
> > However, high-level language may have data structures with
> > non-trivial invariants. If we abort modification in the
> > middle data structures may be left in inconsistent state.
> <
> I might interject at this instant, that My 66000 has this kind of
> behavior with its ATOMIC events (multiple word ATOMICs.)
> If the ATOMIC event fails to complete, control is transferred
> to a place where SW understands that it is no longer "IN" the
> ATOMIC event. Exceptions and interrupts terminate the
> ATOMIC event and perform said transfer of control, there are
> branch instructions which can conditionally transfer control
> out of the ATOMIC event and thus terminate it uncessfully.
> <
> One of the reason I inverted it was so that a concurrent data
> structure could have an element moved from one location in
> the CDS to another location without every being detected as
> "NOT IN" the CDS. Normal ATOMIC events (such as Compare
> double swap double) cannot perform this. This improves the
> invariants while reducing the number of ATOMIC events.
> <
> What I don't understand about OP's statement is when we might
> need such an invariant manifest when we are not also doing some-
> thing that needs to smell ATOMIC. Can OP expand on this ?

Main issue are invariants expected by garbage collector. Extreme,
but simple case is when garbage collector runs: this is "stop
the world" garbage collector, so no other high-level code can
run during garbage collection (garbage collector is in the
same language, but written only using constructs that do
not use normal memory allocation). Garbage collector
is simple, because when it finishes it checks flags for
deferred interrupts. More typical example are function
prologues and epilogues: garbage collector is looking at stack
and needs well-formed stack frames. Once function prologue
is done runtime system can call high-level signal handler
which will build its own stack frame. When high-level
signal handler returns interrupted routine may continue
its work. But if signal handler decides to throw exception,
it will properly unwind stack up to corresponding handler.

Another example is memory allocation: various data structurs
needs to be properly initilized before garbage collector
is allowed to see them.

Yet another (quit frequent) example are derived pointers.
When accessing arrays generated code normally uses base + index
addresing mode. But in many cases it must temporarly create
base+index in a register. Garbage collector can only handle
pointers to start of an object, so garbage collection is
allowed only when no register contains derived pointers
(like base + index form). Yet another thing are temporary
values in registers. Garbage collector deals with tagged values
and pointers. Due to low bit tags garbage collector sees that
tagged values are not pointers and skips them. But untagged
(machine) integer can not appear in place when pointer can
appear, because garbage collector would have no way to distinguish
such integer from a pointer. Currently there is fixed division,
some register contain tagged values, some untagged ones.
But there are also temporary (scratch) registers which
may contain both tagged and untagged values. Garbage
collection is not allowed when a scratch register may contain
a pointer. Scratch register are short lived and after
few instructions all scratch registers are dead.

Now, your ATIMIC construct could help, but it would be used
quite a lot. My guesstimate is that more than 50% of code
would end as member of ATIMIC section. Most section would
be quite short (2-5 instructions), but some would go into
hundreds of instructions. I a bit worried about performance
impact of so many ATIMICs, given that my use does not really
require special warranties with respect to memory (beyond
normal consistency between thread an interrupt handler).

> <
> > So, what is needed is transfer of control to handler at
> > next safepoint, that is at next place where program may be
> > safely interrupted.
> <
> An interrupt, be definition, is asynchronous to the program.
> Indeed, it is foreign to the program, the program should know
> nothing about it except that it happened and control has
> returned.
> <
> Does OP really mean interrupt, here ?
> <
> Could OP mean exception instead ?

Concretly, I have Linux signals. They are asynchonous, but
desired effect is that executing code sees data structures
modified by signal handler and signal handler may pass control
to different place. Signal handler is allowed to allocate
memory, so may trigger garbage collection. Conseqently, when
actual signal handler is allowed to run it must be at point
when garbage collection is safe. There may be other constraints,
for example related to hash tables, but garbage collection
is major issue and it is solved then other problems should be
solvable.

> <
> > I assume that high-level language
> > compiler knows where safepoints are, so the only problem
> > is how to perform control transfer from safepoint to
> > handler. This is essentially what (in)famous "came from"
> > instruction is doing, but I am not aware of any real
> > hardware implementing "came from"...
> >
> > Possible solutions:
> <
> From above to establish context::
> > Problem: We want to code in high-level language and we want
> > to respond to asynchronous events. Simplest example may
> > by timeout (response to timer interrupt). Or we may wish
> > to change what the program is doing in response to external
> > event.
> <
> Why not have the asynchronous event create a worklist and when
> the program gets around to checking for new elements on the
> asynchronous work list, it devotes some resources to making that
> work happen. Thus, the only thing the asynchronous handler would
> be doing is to lob units of work on said worklist (probably ATOMICally.)
> <
> This is basically what interrupt handlers do today--the lob work onto
> the worklist and dismiss the interrupt. then they schedule the OS
> which looks at the worklist (job queue) which then context switches
> into the real handler, and performs a unit or work; then it all unwinds
> so control eventually returns to interrupted program.

In a sense it is 1) below. Except for that I do not have scheduler,
so main thread must check for flags and run deferred handlers.
This works, but has major performance problem.

> > 1) Set a flag in signal handler and check for the flag at
> > each safepoint. Low-level variant od this would keep
> > interrupts disabled most of the time and enable them
> > only at safepoints. This is problematic, because
> > checking inside tight loop may lead to significant
> > performance drop. Not checking inside loop may
> > lead to long delay before reaction to external signal.
> > Inserting checking code by hand could work, but is
> > error-prone and labor-intensive, so I want automatic
> > solution, that is compiler generated checks.
> > 2) Using debug registers: debug register causes transfer
> > to handler after arriving at designated address. This
> > is quite close to what "came from" should do and would
> > be a satisfactory solution. Unfortunately, debug
> > registers are not standard part of architecture and
> > access to debug registers may be restricted by operating
> > system.
> > 3) Separate cleanup routines: each instruction would have
> > associated cleanup routine which will continue computations
> > up to safepoint, but then transfer control to handler.
> > This may be quite satisfactory from performance point
> > of view, but require quite a lot of code.
> > 4) Modyfing code to replace instruction at safepoint
> > by jump. This has usual disadvantages of self-modyfying
> > code, but otherwise looks reasonable.
> > 5) Dynamicaly generating cleanup code: we could copy code
> > from current instruction pointer up to setpoint and add
> > jump to handler at the end. Assuming that code is position
> > independent this should work and is resonably simple. We
> > avoid modification of "normal code", but it is not clear
> > for me if modern CPU-s like it better than 4.
> > 6) Interpret machine instructions up to safepoint. Shuld work,
> > but is lot of code and potentialy slow.
> > 7) Modification of 3 and 6: generate cleanups as bytecode and
> > interpret it. IIUC this is essentially what DWARF is doing
> > to handle C++ exceptions. My impression is that this is
> > complicated to implement, requires a lot of code space and
> > is slow a runtime. OTOH less complicated than 6, probably
> > runs faster than 6 and needs less code space than 3.
> >
> > I wonder if there is other possible implementation that I
> > overlooked? And advantages/disadvantages that I overlooked?
> <
> 2 level interrupt handling:
> <
> First level creates a unit of work on the job queue and dismisses interrupt.
> If work was put on job queue, then invoke OS scheduler, otherwise return
> from interrupt. This level has to be short and fast doing as little as possible
> to keep interrupt responsiveness high.
> <
> Second level takes unit of work off job queue and processes the unit of work.
> When job queue is empty, return control back to interrupted program. This
> level only has to methodologically work thought the job queue.
> <
> We have been doing it this way for at least 6 decades.

On 2021-07-31, antispam@math.uni.wroc.pl <antispam@math.uni.wroc.pl> wrote:
> MitchAlsup <MitchAlsup@aol.com> wrote:
>> On Friday, July 30, 2021 at 4:47:22 PM UTC-5, anti...@math.uni.wroc.pl wrote:
>> > This is more question of implementating high-level languages,
>> > but possible answers depend on computer architecture.
>> >
>> > Problem: We want to code in high-level language and we want
>> > to respond to asynchronous events. Simplest example may
>> > by timeout (response to timer interrupt). Or we may wish
>> > to change what the program is doing in response to external
>> > event. At hardware level there are interrupt, at operating
>> > system level we may get signals, so no problem at low level.
>> > However, high-level language may have data structures with
>> > non-trivial invariants. If we abort modification in the
>> > middle data structures may be left in inconsistent state.
>> <
>> I might interject at this instant, that My 66000 has this kind of
>> behavior with its ATOMIC events (multiple word ATOMICs.)
>> If the ATOMIC event fails to complete, control is transferred
>> to a place where SW understands that it is no longer "IN" the
>> ATOMIC event. Exceptions and interrupts terminate the
>> ATOMIC event and perform said transfer of control, there are
>> branch instructions which can conditionally transfer control
>> out of the ATOMIC event and thus terminate it uncessfully.
>> <
>> One of the reason I inverted it was so that a concurrent data
>> structure could have an element moved from one location in
>> the CDS to another location without every being detected as
>> "NOT IN" the CDS. Normal ATOMIC events (such as Compare
>> double swap double) cannot perform this. This improves the
>> invariants while reducing the number of ATOMIC events.
>> <
>> What I don't understand about OP's statement is when we might
>> need such an invariant manifest when we are not also doing some-
>> thing that needs to smell ATOMIC. Can OP expand on this ?
>
> Main issue are invariants expected by garbage collector. Extreme,
> but simple case is when garbage collector runs: this is "stop
> the world" garbage collector, so no other high-level code can
> run during garbage collection (garbage collector is in the
> same language, but written only using constructs that do
> not use normal memory allocation). Garbage collector
> is simple, because when it finishes it checks flags for
> deferred interrupts. More typical example are function
> prologues and epilogues: garbage collector is looking at stack
> and needs well-formed stack frames. Once function prologue
> is done runtime system can call high-level signal handler
> which will build its own stack frame. When high-level
> signal handler returns interrupted routine may continue
> its work. But if signal handler decides to throw exception,
> it will properly unwind stack up to corresponding handler.
>
> Another example is memory allocation: various data structurs
> needs to be properly initilized before garbage collector
> is allowed to see them.
>
> Yet another (quit frequent) example are derived pointers.
> When accessing arrays generated code normally uses base + index
> addresing mode. But in many cases it must temporarly create
> base+index in a register. Garbage collector can only handle
> pointers to start of an object, so garbage collection is
> allowed only when no register contains derived pointers
> (like base + index form). Yet another thing are temporary
> values in registers. Garbage collector deals with tagged values
> and pointers. Due to low bit tags garbage collector sees that
> tagged values are not pointers and skips them. But untagged
> (machine) integer can not appear in place when pointer can
> appear, because garbage collector would have no way to distinguish
> such integer from a pointer. Currently there is fixed division,
> some register contain tagged values, some untagged ones.
> But there are also temporary (scratch) registers which
> may contain both tagged and untagged values. Garbage
> collection is not allowed when a scratch register may contain
> a pointer. Scratch register are short lived and after
> few instructions all scratch registers are dead.
>
> Now, your ATIMIC construct could help, but it would be used
> quite a lot. My guesstimate is that more than 50% of code
> would end as member of ATIMIC section. Most section would
> be quite short (2-5 instructions), but some would go into
> hundreds of instructions. I a bit worried about performance
> impact of so many ATIMICs, given that my use does not really
> require special warranties with respect to memory (beyond
> normal consistency between thread an interrupt handler).
>
>> <
>> > So, what is needed is transfer of control to handler at
>> > next safepoint, that is at next place where program may be
>> > safely interrupted.
>> <
>> An interrupt, be definition, is asynchronous to the program.
>> Indeed, it is foreign to the program, the program should know
>> nothing about it except that it happened and control has
>> returned.
>> <
>> Does OP really mean interrupt, here ?
>> <
>> Could OP mean exception instead ?
>
> Concretly, I have Linux signals. They are asynchonous, but
> desired effect is that executing code sees data structures
> modified by signal handler and signal handler may pass control
> to different place.

Signal handler is allowed to allocate
> memory, so may trigger garbage collection.

no it is not:
first read man page:
https://man7.org/linux/man-pages/man7/signal-safety.7.html

--
bmaxa now listens Yammat FM

On 2021-07-31, Branimir Maksimovic <branimir.maksimovic@gmail.com> wrote:
> On 2021-07-31, antispam@math.uni.wroc.pl <antispam@math.uni.wroc.pl> wrote:
>> MitchAlsup <MitchAlsup@aol.com> wrote:
>>> On Friday, July 30, 2021 at 4:47:22 PM UTC-5, anti...@math.uni.wroc.pl wrote:
>>> > This is more question of implementating high-level languages,
>>> > but possible answers depend on computer architecture.
>>> >
>>> > Problem: We want to code in high-level language and we want
>>> > to respond to asynchronous events. Simplest example may
>>> > by timeout (response to timer interrupt). Or we may wish
>>> > to change what the program is doing in response to external
>>> > event. At hardware level there are interrupt, at operating
>>> > system level we may get signals, so no problem at low level.
>>> > However, high-level language may have data structures with
>>> > non-trivial invariants. If we abort modification in the
>>> > middle data structures may be left in inconsistent state.
>>> <
>>> I might interject at this instant, that My 66000 has this kind of
>>> behavior with its ATOMIC events (multiple word ATOMICs.)
>>> If the ATOMIC event fails to complete, control is transferred
>>> to a place where SW understands that it is no longer "IN" the
>>> ATOMIC event. Exceptions and interrupts terminate the
>>> ATOMIC event and perform said transfer of control, there are
>>> branch instructions which can conditionally transfer control
>>> out of the ATOMIC event and thus terminate it uncessfully.
>>> <
>>> One of the reason I inverted it was so that a concurrent data
>>> structure could have an element moved from one location in
>>> the CDS to another location without every being detected as
>>> "NOT IN" the CDS. Normal ATOMIC events (such as Compare
>>> double swap double) cannot perform this. This improves the
>>> invariants while reducing the number of ATOMIC events.
>>> <
>>> What I don't understand about OP's statement is when we might
>>> need such an invariant manifest when we are not also doing some-
>>> thing that needs to smell ATOMIC. Can OP expand on this ?
>>
>> Main issue are invariants expected by garbage collector. Extreme,
>> but simple case is when garbage collector runs: this is "stop
>> the world" garbage collector, so no other high-level code can
>> run during garbage collection (garbage collector is in the
>> same language, but written only using constructs that do
>> not use normal memory allocation). Garbage collector
>> is simple, because when it finishes it checks flags for
>> deferred interrupts. More typical example are function
>> prologues and epilogues: garbage collector is looking at stack
>> and needs well-formed stack frames. Once function prologue
>> is done runtime system can call high-level signal handler
>> which will build its own stack frame. When high-level
>> signal handler returns interrupted routine may continue
>> its work. But if signal handler decides to throw exception,
>> it will properly unwind stack up to corresponding handler.
>>
>> Another example is memory allocation: various data structurs
>> needs to be properly initilized before garbage collector
>> is allowed to see them.
>>
>> Yet another (quit frequent) example are derived pointers.
>> When accessing arrays generated code normally uses base + index
>> addresing mode. But in many cases it must temporarly create
>> base+index in a register. Garbage collector can only handle
>> pointers to start of an object, so garbage collection is
>> allowed only when no register contains derived pointers
>> (like base + index form). Yet another thing are temporary
>> values in registers. Garbage collector deals with tagged values
>> and pointers. Due to low bit tags garbage collector sees that
>> tagged values are not pointers and skips them. But untagged
>> (machine) integer can not appear in place when pointer can
>> appear, because garbage collector would have no way to distinguish
>> such integer from a pointer. Currently there is fixed division,
>> some register contain tagged values, some untagged ones.
>> But there are also temporary (scratch) registers which
>> may contain both tagged and untagged values. Garbage
>> collection is not allowed when a scratch register may contain
>> a pointer. Scratch register are short lived and after
>> few instructions all scratch registers are dead.
>>
>> Now, your ATIMIC construct could help, but it would be used
>> quite a lot. My guesstimate is that more than 50% of code
>> would end as member of ATIMIC section. Most section would
>> be quite short (2-5 instructions), but some would go into
>> hundreds of instructions. I a bit worried about performance
>> impact of so many ATIMICs, given that my use does not really
>> require special warranties with respect to memory (beyond
>> normal consistency between thread an interrupt handler).
>>
>>> <
>>> > So, what is needed is transfer of control to handler at
>>> > next safepoint, that is at next place where program may be
>>> > safely interrupted.
>>> <
>>> An interrupt, be definition, is asynchronous to the program.
>>> Indeed, it is foreign to the program, the program should know
>>> nothing about it except that it happened and control has
>>> returned.
>>> <
>>> Does OP really mean interrupt, here ?
>>> <
>>> Could OP mean exception instead ?
>>
>> Concretly, I have Linux signals. They are asynchonous, but
>> desired effect is that executing code sees data structures
>> modified by signal handler and signal handler may pass control
>> to different place.
>
>
> Signal handler is allowed to allocate
>> memory, so may trigger garbage collection.
>
> no it is not:
> first read man page:
> https://man7.org/linux/man-pages/man7/signal-safety.7.html
>
>
BTW look up in GC implementation of "stop the world". It probably
uses signals. Use same tehcnique to implement user space scheduler.

--
bmaxa now listens Yammat FM

On 2021-07-31, Branimir Maksimovic <branimir.maksimovic@gmail.com> wrote:
> On 2021-07-31, Branimir Maksimovic <branimir.maksimovic@gmail.com> wrote:
>> On 2021-07-31, antispam@math.uni.wroc.pl <antispam@math.uni.wroc.pl> wrote:
>>> MitchAlsup <MitchAlsup@aol.com> wrote:
>>>> On Friday, July 30, 2021 at 4:47:22 PM UTC-5, anti...@math.uni.wroc.pl wrote:
>>>> > This is more question of implementating high-level languages,
>>>> > but possible answers depend on computer architecture.
>>>> >
>>>> > Problem: We want to code in high-level language and we want
>>>> > to respond to asynchronous events. Simplest example may
>>>> > by timeout (response to timer interrupt). Or we may wish
>>>> > to change what the program is doing in response to external
>>>> > event. At hardware level there are interrupt, at operating
>>>> > system level we may get signals, so no problem at low level.
>>>> > However, high-level language may have data structures with
>>>> > non-trivial invariants. If we abort modification in the
>>>> > middle data structures may be left in inconsistent state.
>>>> <
>>>> I might interject at this instant, that My 66000 has this kind of
>>>> behavior with its ATOMIC events (multiple word ATOMICs.)
>>>> If the ATOMIC event fails to complete, control is transferred
>>>> to a place where SW understands that it is no longer "IN" the
>>>> ATOMIC event. Exceptions and interrupts terminate the
>>>> ATOMIC event and perform said transfer of control, there are
>>>> branch instructions which can conditionally transfer control
>>>> out of the ATOMIC event and thus terminate it uncessfully.
>>>> <
>>>> One of the reason I inverted it was so that a concurrent data
>>>> structure could have an element moved from one location in
>>>> the CDS to another location without every being detected as
>>>> "NOT IN" the CDS. Normal ATOMIC events (such as Compare
>>>> double swap double) cannot perform this. This improves the
>>>> invariants while reducing the number of ATOMIC events.
>>>> <
>>>> What I don't understand about OP's statement is when we might
>>>> need such an invariant manifest when we are not also doing some-
>>>> thing that needs to smell ATOMIC. Can OP expand on this ?
>>>
>>> Main issue are invariants expected by garbage collector. Extreme,
>>> but simple case is when garbage collector runs: this is "stop
>>> the world" garbage collector, so no other high-level code can
>>> run during garbage collection (garbage collector is in the
>>> same language, but written only using constructs that do
>>> not use normal memory allocation). Garbage collector
>>> is simple, because when it finishes it checks flags for
>>> deferred interrupts. More typical example are function
>>> prologues and epilogues: garbage collector is looking at stack
>>> and needs well-formed stack frames. Once function prologue
>>> is done runtime system can call high-level signal handler
>>> which will build its own stack frame. When high-level
>>> signal handler returns interrupted routine may continue
>>> its work. But if signal handler decides to throw exception,
>>> it will properly unwind stack up to corresponding handler.
>>>
>>> Another example is memory allocation: various data structurs
>>> needs to be properly initilized before garbage collector
>>> is allowed to see them.
>>>
>>> Yet another (quit frequent) example are derived pointers.
>>> When accessing arrays generated code normally uses base + index
>>> addresing mode. But in many cases it must temporarly create
>>> base+index in a register. Garbage collector can only handle
>>> pointers to start of an object, so garbage collection is
>>> allowed only when no register contains derived pointers
>>> (like base + index form). Yet another thing are temporary
>>> values in registers. Garbage collector deals with tagged values
>>> and pointers. Due to low bit tags garbage collector sees that
>>> tagged values are not pointers and skips them. But untagged
>>> (machine) integer can not appear in place when pointer can
>>> appear, because garbage collector would have no way to distinguish
>>> such integer from a pointer. Currently there is fixed division,
>>> some register contain tagged values, some untagged ones.
>>> But there are also temporary (scratch) registers which
>>> may contain both tagged and untagged values. Garbage
>>> collection is not allowed when a scratch register may contain
>>> a pointer. Scratch register are short lived and after
>>> few instructions all scratch registers are dead.
>>>
>>> Now, your ATIMIC construct could help, but it would be used
>>> quite a lot. My guesstimate is that more than 50% of code
>>> would end as member of ATIMIC section. Most section would
>>> be quite short (2-5 instructions), but some would go into
>>> hundreds of instructions. I a bit worried about performance
>>> impact of so many ATIMICs, given that my use does not really
>>> require special warranties with respect to memory (beyond
>>> normal consistency between thread an interrupt handler).
>>>
>>>> <
>>>> > So, what is needed is transfer of control to handler at
>>>> > next safepoint, that is at next place where program may be
>>>> > safely interrupted.
>>>> <
>>>> An interrupt, be definition, is asynchronous to the program.
>>>> Indeed, it is foreign to the program, the program should know
>>>> nothing about it except that it happened and control has
>>>> returned.
>>>> <
>>>> Does OP really mean interrupt, here ?
>>>> <
>>>> Could OP mean exception instead ?
>>>
>>> Concretly, I have Linux signals. They are asynchonous, but
>>> desired effect is that executing code sees data structures
>>> modified by signal handler and signal handler may pass control
>>> to different place.
>>
>>
>> Signal handler is allowed to allocate
>>> memory, so may trigger garbage collection.
>>
>> no it is not:
>> first read man page:
>> https://man7.org/linux/man-pages/man7/signal-safety.7.html
>>
>>
> BTW look up in GC implementation of "stop the world". It probably
> uses signals. Use same tehcnique to implement user space scheduler.
>
Heh, on the second thought, perhaps you don't know that handling
of async events nowdays are done by starting thread or forking process?
Perhaps you don't even need userspace threads :P
Golang implements cooperative, Haskell I think real multi tasking.

--
bmaxa now listens Yammat FM

antispam@math.uni.wroc.pl <antispam@math.uni.wroc.pl> schrieb:

> Problem: We want to code in high-level language and we want
> to respond to asynchronous events.

Have you looked at the way Ada handles interrupts?
https://www.adacore.com/gems/ada-gem-13 looks like a good first
read, but of course assumes some familiarity with Ada which I
don't have at that level.

On 2021-07-31, Thomas Koenig <tkoenig@netcologne.de> wrote:
> antispam@math.uni.wroc.pl <antispam@math.uni.wroc.pl> schrieb:
>
>> Problem: We want to code in high-level language and we want
>> to respond to asynchronous events.
>
> Have you looked at the way Ada handles interrupts?
> https://www.adacore.com/gems/ada-gem-13 looks like a good first
> read, but of course assumes some familiarity with Ada which I
> don't have at that level.
He uses OS, that is Linux, this is for working wihout OS....
Besides, nobody here can figure out that he doesn;'t know
what is he talking about :P

--
bmaxa now listens Ob-Neob Radio

On 30/07/2021 23:47, antispam@math.uni.wroc.pl wrote:
> This is more question of implementating high-level languages,
> but possible answers depend on computer architecture.
>
> Problem: We want to code in high-level language and we want
> to respond to asynchronous events. Simplest example may
> by timeout (response to timer interrupt). Or we may wish
> to change what the program is doing in response to external
> event. At hardware level there are interrupt, at operating
> system level we may get signals, so no problem at low level.
> However, high-level language may have data structures with
> non-trivial invariants. If we abort modification in the
> middle data structures may be left in inconsistent state.
> So, what is needed is transfer of control to handler at
> next safepoint, that is at next place where program may be
> safely interrupted. I assume that high-level language
> compiler knows where safepoints are, so the only problem
> is how to perform control transfer from safepoint to
> handler. This is essentially what (in)famous "came from"
> instruction is doing, but I am not aware of any real
> hardware implementing "came from"...
>
> Possible solutions:
>
> 1) Set a flag in signal handler and check for the flag at
> each safepoint. Low-level variant od this would keep
> interrupts disabled most of the time and enable them
> only at safepoints. This is problematic, because
> checking inside tight loop may lead to significant
> performance drop. Not checking inside loop may
> lead to long delay before reaction to external signal.
> Inserting checking code by hand could work, but is
> error-prone and labor-intensive, so I want automatic
> solution, that is compiler generated checks.
> 2) Using debug registers: debug register causes transfer
> to handler after arriving at designated address. This
> is quite close to what "came from" should do and would
> be a satisfactory solution. Unfortunately, debug
> registers are not standard part of architecture and
> access to debug registers may be restricted by operating
> system.
> 3) Separate cleanup routines: each instruction would have
> associated cleanup routine which will continue computations
> up to safepoint, but then transfer control to handler.
> This may be quite satisfactory from performance point
> of view, but require quite a lot of code.
> 4) Modyfing code to replace instruction at safepoint
> by jump. This has usual disadvantages of self-modyfying
> code, but otherwise looks reasonable.
> 5) Dynamicaly generating cleanup code: we could copy code
> from current instruction pointer up to setpoint and add
> jump to handler at the end. Assuming that code is position
> independent this should work and is resonably simple. We
> avoid modification of "normal code", but it is not clear
> for me if modern CPU-s like it better than 4.
> 6) Interpret machine instructions up to safepoint. Shuld work,
> but is lot of code and potentialy slow.
> 7) Modification of 3 and 6: generate cleanups as bytecode and
> interpret it. IIUC this is essentially what DWARF is doing
> to handle C++ exceptions. My impression is that this is
> complicated to implement, requires a lot of code space and
> is slow a runtime. OTOH less complicated than 6, probably
> runs faster than 6 and needs less code space than 3.
>
> I wonder if there is other possible implementation that I
> overlooked? And advantages/disadvantages that I overlooked?
>

I've always thought a "disable interrupts for the next N instructions",
with "N" being a small immediate constant, would be an extremely useful
instruction on the kind of devices I use (single cpu microcontrollers).
This instruction should work regardless of the current interrupt enable
status, making it significantly more efficient than the usual store old
status, disable interrupts, restore old status dance. It could also be
allowable from user mode safely, unlike normal interrupt disable, since
it is only temporary. And then you would have an easy and safe way to
make short multi-instruction atomic sections, in a way that could be
used by any language.

That would not completely solve your complex invariant problem here, but
it could be used to have atomic logs/trackers of the state of the
object, allowing the program to identify and recover from inconsistent
states.

On 2021-07-31, David Brown <david.brown@hesbynett.no> wrote:
> On 30/07/2021 23:47, antispam@math.uni.wroc.pl wrote:
>> This is more question of implementating high-level languages,
>> but possible answers depend on computer architecture.
>>
>> Problem: We want to code in high-level language and we want
>> to respond to asynchronous events. Simplest example may
>> by timeout (response to timer interrupt). Or we may wish
>> to change what the program is doing in response to external
>> event. At hardware level there are interrupt, at operating
>> system level we may get signals, so no problem at low level.
>> However, high-level language may have data structures with
>> non-trivial invariants. If we abort modification in the
>> middle data structures may be left in inconsistent state.
>> So, what is needed is transfer of control to handler at
>> next safepoint, that is at next place where program may be
>> safely interrupted. I assume that high-level language
>> compiler knows where safepoints are, so the only problem
>> is how to perform control transfer from safepoint to
>> handler. This is essentially what (in)famous "came from"
>> instruction is doing, but I am not aware of any real
>> hardware implementing "came from"...
>>
>> Possible solutions:
>>
>> 1) Set a flag in signal handler and check for the flag at
>> each safepoint. Low-level variant od this would keep
>> interrupts disabled most of the time and enable them
>> only at safepoints. This is problematic, because
>> checking inside tight loop may lead to significant
>> performance drop. Not checking inside loop may
>> lead to long delay before reaction to external signal.
>> Inserting checking code by hand could work, but is
>> error-prone and labor-intensive, so I want automatic
>> solution, that is compiler generated checks.
>> 2) Using debug registers: debug register causes transfer
>> to handler after arriving at designated address. This
>> is quite close to what "came from" should do and would
>> be a satisfactory solution. Unfortunately, debug
>> registers are not standard part of architecture and
>> access to debug registers may be restricted by operating
>> system.
>> 3) Separate cleanup routines: each instruction would have
>> associated cleanup routine which will continue computations
>> up to safepoint, but then transfer control to handler.
>> This may be quite satisfactory from performance point
>> of view, but require quite a lot of code.
>> 4) Modyfing code to replace instruction at safepoint
>> by jump. This has usual disadvantages of self-modyfying
>> code, but otherwise looks reasonable.
>> 5) Dynamicaly generating cleanup code: we could copy code
>> from current instruction pointer up to setpoint and add
>> jump to handler at the end. Assuming that code is position
>> independent this should work and is resonably simple. We
>> avoid modification of "normal code", but it is not clear
>> for me if modern CPU-s like it better than 4.
>> 6) Interpret machine instructions up to safepoint. Shuld work,
>> but is lot of code and potentialy slow.
>> 7) Modification of 3 and 6: generate cleanups as bytecode and
>> interpret it. IIUC this is essentially what DWARF is doing
>> to handle C++ exceptions. My impression is that this is
>> complicated to implement, requires a lot of code space and
>> is slow a runtime. OTOH less complicated than 6, probably
>> runs faster than 6 and needs less code space than 3.
>>
>> I wonder if there is other possible implementation that I
>> overlooked? And advantages/disadvantages that I overlooked?
>>
>
> I've always thought a "disable interrupts for the next N instructions",
> with "N" being a small immediate constant, would be an extremely useful
> instruction on the kind of devices I use (single cpu microcontrollers).
> This instruction should work regardless of the current interrupt enable
> status, making it significantly more efficient than the usual store old
> status, disable interrupts, restore old status dance. It could also be
> allowable from user mode safely, unlike normal interrupt disable, since
> it is only temporary. And then you would have an easy and safe way to
> make short multi-instruction atomic sections, in a way that could be
> used by any language.
>
> That would not completely solve your complex invariant problem here, but
> it could be used to have atomic logs/trackers of the state of the
> object, allowing the program to identify and recover from inconsistent
> states.
>
Except that you cannot disable interupts in signal handler, neither
touch (because of that) any global variable/flag, nor call any
sideffect function....

--
bmaxa now listens Ob-Neob Radio

On 2021-07-31, Branimir Maksimovic <branimir.maksimovic@gmail.com> wrote:
> On 2021-07-31, David Brown <david.brown@hesbynett.no> wrote:
>> On 30/07/2021 23:47, antispam@math.uni.wroc.pl wrote:
>>> This is more question of implementating high-level languages,
>>> but possible answers depend on computer architecture.
>>>
>>> Problem: We want to code in high-level language and we want
>>> to respond to asynchronous events. Simplest example may
>>> by timeout (response to timer interrupt). Or we may wish
>>> to change what the program is doing in response to external
>>> event. At hardware level there are interrupt, at operating
>>> system level we may get signals, so no problem at low level.
>>> However, high-level language may have data structures with
>>> non-trivial invariants. If we abort modification in the
>>> middle data structures may be left in inconsistent state.
>>> So, what is needed is transfer of control to handler at
>>> next safepoint, that is at next place where program may be
>>> safely interrupted. I assume that high-level language
>>> compiler knows where safepoints are, so the only problem
>>> is how to perform control transfer from safepoint to
>>> handler. This is essentially what (in)famous "came from"
>>> instruction is doing, but I am not aware of any real
>>> hardware implementing "came from"...
>>>
>>> Possible solutions:
>>>
>>> 1) Set a flag in signal handler and check for the flag at
>>> each safepoint. Low-level variant od this would keep
>>> interrupts disabled most of the time and enable them
>>> only at safepoints. This is problematic, because
>>> checking inside tight loop may lead to significant
>>> performance drop. Not checking inside loop may
>>> lead to long delay before reaction to external signal.
>>> Inserting checking code by hand could work, but is
>>> error-prone and labor-intensive, so I want automatic
>>> solution, that is compiler generated checks.
>>> 2) Using debug registers: debug register causes transfer
>>> to handler after arriving at designated address. This
>>> is quite close to what "came from" should do and would
>>> be a satisfactory solution. Unfortunately, debug
>>> registers are not standard part of architecture and
>>> access to debug registers may be restricted by operating
>>> system.
>>> 3) Separate cleanup routines: each instruction would have
>>> associated cleanup routine which will continue computations
>>> up to safepoint, but then transfer control to handler.
>>> This may be quite satisfactory from performance point
>>> of view, but require quite a lot of code.
>>> 4) Modyfing code to replace instruction at safepoint
>>> by jump. This has usual disadvantages of self-modyfying
>>> code, but otherwise looks reasonable.
>>> 5) Dynamicaly generating cleanup code: we could copy code
>>> from current instruction pointer up to setpoint and add
>>> jump to handler at the end. Assuming that code is position
>>> independent this should work and is resonably simple. We
>>> avoid modification of "normal code", but it is not clear
>>> for me if modern CPU-s like it better than 4.
>>> 6) Interpret machine instructions up to safepoint. Shuld work,
>>> but is lot of code and potentialy slow.
>>> 7) Modification of 3 and 6: generate cleanups as bytecode and
>>> interpret it. IIUC this is essentially what DWARF is doing
>>> to handle C++ exceptions. My impression is that this is
>>> complicated to implement, requires a lot of code space and
>>> is slow a runtime. OTOH less complicated than 6, probably
>>> runs faster than 6 and needs less code space than 3.
>>>
>>> I wonder if there is other possible implementation that I
>>> overlooked? And advantages/disadvantages that I overlooked?
>>>
>>
>> I've always thought a "disable interrupts for the next N instructions",
>> with "N" being a small immediate constant, would be an extremely useful
>> instruction on the kind of devices I use (single cpu microcontrollers).
>> This instruction should work regardless of the current interrupt enable
>> status, making it significantly more efficient than the usual store old
>> status, disable interrupts, restore old status dance. It could also be
>> allowable from user mode safely, unlike normal interrupt disable, since
>> it is only temporary. And then you would have an easy and safe way to
>> make short multi-instruction atomic sections, in a way that could be
>> used by any language.
>>
>> That would not completely solve your complex invariant problem here, but
>> it could be used to have atomic logs/trackers of the state of the
>> object, allowing the program to identify and recover from inconsistent
>> states.
>>
> Except that you cannot disable interupts in signal handler, neither
> touch (because of that) any global variable/flag, nor call any
> sideffect function....
>

Problem is that signal handler is equivalent of interrupt service routine.
It can be interupted by same interrupt/signal and called again. If you disable
interrupts for longer time (than necessary to service whatever in driver under
Linux),
it won't be called and may break OS.
Also he is mentioning GC in this story :P
Without OS no problem, but he is also mentioning Linux.

--
bmaxa now listens Ob-Neob Radio

antispam@math.uni.wroc.pl wrote:
> This is more question of implementating high-level languages,
> but possible answers depend on computer architecture.
>
> Problem: We want to code in high-level language and we want
> to respond to asynchronous events. Simplest example may
> by timeout (response to timer interrupt). Or we may wish
> to change what the program is doing in response to external
> event. At hardware level there are interrupt, at operating
> system level we may get signals, so no problem at low level.
> However, high-level language may have data structures with
> non-trivial invariants. If we abort modification in the
> middle data structures may be left in inconsistent state.
> So, what is needed is transfer of control to handler at
> next safepoint, that is at next place where program may be
> safely interrupted. I assume that high-level language
> compiler knows where safepoints are, so the only problem
> is how to perform control transfer from safepoint to
> handler. This is essentially what (in)famous "came from"
> instruction is doing, but I am not aware of any real
> hardware implementing "came from"...
>
....
> I wonder if there is other possible implementation that I
> overlooked? And advantages/disadvantages that I overlooked?

Insert a load from a fixed address (thread specific, if you like) at
your safepoint. When you want to stop some thread, disable read
permissions for that address, and let the thread take a trap. In
practice the overhead in the common case is negligible because the
load is speculated and its value is never used.

There is some overhead (on the order of a microsecond) though, from
the trip through the kernel when the trap actually happens, but it's
usually rare enough that this overhead doesn't matter. It would be
nice to have user-space fault handlers to make this overhead go away.

Andrew.

On 2021-07-31, aph@littlepinkcloud.invalid <aph@littlepinkcloud.invalid> wrote:
> antispam@math.uni.wroc.pl wrote:
>> This is more question of implementating high-level languages,
>> but possible answers depend on computer architecture.
>>
>> Problem: We want to code in high-level language and we want
>> to respond to asynchronous events. Simplest example may
>> by timeout (response to timer interrupt). Or we may wish
>> to change what the program is doing in response to external
>> event. At hardware level there are interrupt, at operating
>> system level we may get signals, so no problem at low level.
>> However, high-level language may have data structures with
>> non-trivial invariants. If we abort modification in the
>> middle data structures may be left in inconsistent state.
>> So, what is needed is transfer of control to handler at
>> next safepoint, that is at next place where program may be
>> safely interrupted. I assume that high-level language
>> compiler knows where safepoints are, so the only problem
>> is how to perform control transfer from safepoint to
>> handler. This is essentially what (in)famous "came from"
>> instruction is doing, but I am not aware of any real
>> hardware implementing "came from"...
>>
> ...
>> I wonder if there is other possible implementation that I
>> overlooked? And advantages/disadvantages that I overlooked?
>
> Insert a load from a fixed address (thread specific, if you like) at
> your safepoint. When you want to stop some thread, disable read
> permissions for that address, and let the thread take a trap. In
> practice the overhead in the common case is negligible because the
> load is speculated and its value is never used.
>
> There is some overhead (on the order of a microsecond) though, from
> the trip through the kernel when the trap actually happens, but it's
> usually rare enough that this overhead doesn't matter. It would be
> nice to have user-space fault handlers to make this overhead go away.
>
> Andrew.
Isn't it simpler just to start another thread which will wait on events? :P
With GC, JIT and all that :P
He is also mentioning memory allocation from signal handler...

--
bmaxa now listens Ob-Neob Radio

Branimir Maksimovic <branimir.maksimovic@gmail.com> wrote:
> On 2021-07-31, antispam@math.uni.wroc.pl <antispam@math.uni.wroc.pl> wrote:
> > MitchAlsup <MitchAlsup@aol.com> wrote:
> >> On Friday, July 30, 2021 at 4:47:22 PM UTC-5, anti...@math.uni.wroc.pl wrote:
> >> > This is more question of implementating high-level languages,
> >> > but possible answers depend on computer architecture.
> >> >
> >> > Problem: We want to code in high-level language and we want
> >> > to respond to asynchronous events. Simplest example may
> >> > by timeout (response to timer interrupt). Or we may wish
> >> > to change what the program is doing in response to external
> >> > event. At hardware level there are interrupt, at operating
> >> > system level we may get signals, so no problem at low level.
> >> > However, high-level language may have data structures with
> >> > non-trivial invariants. If we abort modification in the
> >> > middle data structures may be left in inconsistent state.
> >> <
> >> I might interject at this instant, that My 66000 has this kind of
> >> behavior with its ATOMIC events (multiple word ATOMICs.)
> >> If the ATOMIC event fails to complete, control is transferred
> >> to a place where SW understands that it is no longer "IN" the
> >> ATOMIC event. Exceptions and interrupts terminate the
> >> ATOMIC event and perform said transfer of control, there are
> >> branch instructions which can conditionally transfer control
> >> out of the ATOMIC event and thus terminate it uncessfully.
> >> <
> >> One of the reason I inverted it was so that a concurrent data
> >> structure could have an element moved from one location in
> >> the CDS to another location without every being detected as
> >> "NOT IN" the CDS. Normal ATOMIC events (such as Compare
> >> double swap double) cannot perform this. This improves the
> >> invariants while reducing the number of ATOMIC events.
> >> <
> >> What I don't understand about OP's statement is when we might
> >> need such an invariant manifest when we are not also doing some-
> >> thing that needs to smell ATOMIC. Can OP expand on this ?
> >
> > Main issue are invariants expected by garbage collector. Extreme,
> > but simple case is when garbage collector runs: this is "stop
> > the world" garbage collector, so no other high-level code can
> > run during garbage collection (garbage collector is in the
> > same language, but written only using constructs that do
> > not use normal memory allocation). Garbage collector
> > is simple, because when it finishes it checks flags for
> > deferred interrupts. More typical example are function
> > prologues and epilogues: garbage collector is looking at stack
> > and needs well-formed stack frames. Once function prologue
> > is done runtime system can call high-level signal handler
> > which will build its own stack frame. When high-level
> > signal handler returns interrupted routine may continue
> > its work. But if signal handler decides to throw exception,
> > it will properly unwind stack up to corresponding handler.
> >
> > Another example is memory allocation: various data structurs
> > needs to be properly initilized before garbage collector
> > is allowed to see them.
> >
> > Yet another (quit frequent) example are derived pointers.
> > When accessing arrays generated code normally uses base + index
> > addresing mode. But in many cases it must temporarly create
> > base+index in a register. Garbage collector can only handle
> > pointers to start of an object, so garbage collection is
> > allowed only when no register contains derived pointers
> > (like base + index form). Yet another thing are temporary
> > values in registers. Garbage collector deals with tagged values
> > and pointers. Due to low bit tags garbage collector sees that
> > tagged values are not pointers and skips them. But untagged
> > (machine) integer can not appear in place when pointer can
> > appear, because garbage collector would have no way to distinguish
> > such integer from a pointer. Currently there is fixed division,
> > some register contain tagged values, some untagged ones.
> > But there are also temporary (scratch) registers which
> > may contain both tagged and untagged values. Garbage
> > collection is not allowed when a scratch register may contain
> > a pointer. Scratch register are short lived and after
> > few instructions all scratch registers are dead.
> >
> > Now, your ATIMIC construct could help, but it would be used
> > quite a lot. My guesstimate is that more than 50% of code
> > would end as member of ATIMIC section. Most section would
> > be quite short (2-5 instructions), but some would go into
> > hundreds of instructions. I a bit worried about performance
> > impact of so many ATIMICs, given that my use does not really
> > require special warranties with respect to memory (beyond
> > normal consistency between thread an interrupt handler).
> >
> >> <
> >> > So, what is needed is transfer of control to handler at
> >> > next safepoint, that is at next place where program may be
> >> > safely interrupted.
> >> <
> >> An interrupt, be definition, is asynchronous to the program.
> >> Indeed, it is foreign to the program, the program should know
> >> nothing about it except that it happened and control has
> >> returned.
> >> <
> >> Does OP really mean interrupt, here ?
> >> <
> >> Could OP mean exception instead ?
> >
> > Concretly, I have Linux signals. They are asynchonous, but
> > desired effect is that executing code sees data structures
> > modified by signal handler and signal handler may pass control
> > to different place.
>
>
> Signal handler is allowed to allocate
> > memory, so may trigger garbage collection.
>
> no it is not:
> first read man page:
> https://man7.org/linux/man-pages/man7/signal-safety.7.html

Sorry, this is irrelevant for me. This page talks about C
library but I am fine with restriction "you can not call
C library from signal handler". But you can make arbitrary
system calls, if needed making sure to bypass possible breakage
due to C library wrapping system calls. So you can call
'mmap' or 'sbrk' to allocate memory. I am talking
about signal handler in high-level language which has
its own memory allocator, using system calls if needed
but independent of C library. And the thing works now
using strategy 1) above. But the drawback is that all
code pays cost of polling and it this cost is substantial.

--
Waldek Hebisch

On 2021-07-31, antispam@math.uni.wroc.pl <antispam@math.uni.wroc.pl> wrote:
> Branimir Maksimovic <branimir.maksimovic@gmail.com> wrote:
>> On 2021-07-31, antispam@math.uni.wroc.pl <antispam@math.uni.wroc.pl> wrote:
>> > MitchAlsup <MitchAlsup@aol.com> wrote:
>> >> On Friday, July 30, 2021 at 4:47:22 PM UTC-5, anti...@math.uni.wroc.pl wrote:
>> >> > This is more question of implementating high-level languages,
>> >> > but possible answers depend on computer architecture.
>> >> >
>> >> > Problem: We want to code in high-level language and we want
>> >> > to respond to asynchronous events. Simplest example may
>> >> > by timeout (response to timer interrupt). Or we may wish
>> >> > to change what the program is doing in response to external
>> >> > event. At hardware level there are interrupt, at operating
>> >> > system level we may get signals, so no problem at low level.
>> >> > However, high-level language may have data structures with
>> >> > non-trivial invariants. If we abort modification in the
>> >> > middle data structures may be left in inconsistent state.
>> >> <
>> >> I might interject at this instant, that My 66000 has this kind of
>> >> behavior with its ATOMIC events (multiple word ATOMICs.)
>> >> If the ATOMIC event fails to complete, control is transferred
>> >> to a place where SW understands that it is no longer "IN" the
>> >> ATOMIC event. Exceptions and interrupts terminate the
>> >> ATOMIC event and perform said transfer of control, there are
>> >> branch instructions which can conditionally transfer control
>> >> out of the ATOMIC event and thus terminate it uncessfully.
>> >> <
>> >> One of the reason I inverted it was so that a concurrent data
>> >> structure could have an element moved from one location in
>> >> the CDS to another location without every being detected as
>> >> "NOT IN" the CDS. Normal ATOMIC events (such as Compare
>> >> double swap double) cannot perform this. This improves the
>> >> invariants while reducing the number of ATOMIC events.
>> >> <
>> >> What I don't understand about OP's statement is when we might
>> >> need such an invariant manifest when we are not also doing some-
>> >> thing that needs to smell ATOMIC. Can OP expand on this ?
>> >
>> > Main issue are invariants expected by garbage collector. Extreme,
>> > but simple case is when garbage collector runs: this is "stop
>> > the world" garbage collector, so no other high-level code can
>> > run during garbage collection (garbage collector is in the
>> > same language, but written only using constructs that do
>> > not use normal memory allocation). Garbage collector
>> > is simple, because when it finishes it checks flags for
>> > deferred interrupts. More typical example are function
>> > prologues and epilogues: garbage collector is looking at stack
>> > and needs well-formed stack frames. Once function prologue
>> > is done runtime system can call high-level signal handler
>> > which will build its own stack frame. When high-level
>> > signal handler returns interrupted routine may continue
>> > its work. But if signal handler decides to throw exception,
>> > it will properly unwind stack up to corresponding handler.
>> >
>> > Another example is memory allocation: various data structurs
>> > needs to be properly initilized before garbage collector
>> > is allowed to see them.
>> >
>> > Yet another (quit frequent) example are derived pointers.
>> > When accessing arrays generated code normally uses base + index
>> > addresing mode. But in many cases it must temporarly create
>> > base+index in a register. Garbage collector can only handle
>> > pointers to start of an object, so garbage collection is
>> > allowed only when no register contains derived pointers
>> > (like base + index form). Yet another thing are temporary
>> > values in registers. Garbage collector deals with tagged values
>> > and pointers. Due to low bit tags garbage collector sees that
>> > tagged values are not pointers and skips them. But untagged
>> > (machine) integer can not appear in place when pointer can
>> > appear, because garbage collector would have no way to distinguish
>> > such integer from a pointer. Currently there is fixed division,
>> > some register contain tagged values, some untagged ones.
>> > But there are also temporary (scratch) registers which
>> > may contain both tagged and untagged values. Garbage
>> > collection is not allowed when a scratch register may contain
>> > a pointer. Scratch register are short lived and after
>> > few instructions all scratch registers are dead.
>> >
>> > Now, your ATIMIC construct could help, but it would be used
>> > quite a lot. My guesstimate is that more than 50% of code
>> > would end as member of ATIMIC section. Most section would
>> > be quite short (2-5 instructions), but some would go into
>> > hundreds of instructions. I a bit worried about performance
>> > impact of so many ATIMICs, given that my use does not really
>> > require special warranties with respect to memory (beyond
>> > normal consistency between thread an interrupt handler).
>> >
>> >> <
>> >> > So, what is needed is transfer of control to handler at
>> >> > next safepoint, that is at next place where program may be
>> >> > safely interrupted.
>> >> <
>> >> An interrupt, be definition, is asynchronous to the program.
>> >> Indeed, it is foreign to the program, the program should know
>> >> nothing about it except that it happened and control has
>> >> returned.
>> >> <
>> >> Does OP really mean interrupt, here ?
>> >> <
>> >> Could OP mean exception instead ?
>> >
>> > Concretly, I have Linux signals. They are asynchonous, but
>> > desired effect is that executing code sees data structures
>> > modified by signal handler and signal handler may pass control
>> > to different place.
>>
>>
>> Signal handler is allowed to allocate
>> > memory, so may trigger garbage collection.
>>
>> no it is not:
>> first read man page:
>> https://man7.org/linux/man-pages/man7/signal-safety.7.html
>
> Sorry, this is irrelevant for me. This page talks about C
> library but I am fine with restriction "you can not call
> C library from signal handler". But you can make arbitrary
> system calls, if needed making sure to bypass possible breakage
> due to C library wrapping system calls. So you can call
> 'mmap' or 'sbrk' to allocate memory. I am talking
> about signal handler in high-level language which has
> its own memory allocator, using system calls if needed
> but independent of C library. And the thing works now
> using strategy 1) above. But the drawback is that all
> code pays cost of polling and it this cost is substantial.
>
signals and threads doesn't like each other.
If you are talking about Linux signals, that is.if you are talking
about your implementation of signals then this is misunderstanding.

--
bmaxa now listens Ob-Neob Radio

Branimir Maksimovic <branimir.maksimovic@gmail.com> wrote:
> On 2021-07-30, antispam@math.uni.wroc.pl <antispam@math.uni.wroc.pl> wrote:
> > This is more question of implementating high-level languages,
> > but possible answers depend on computer architecture.
> >
> > Problem: We want to code in high-level language and we want
> > to respond to asynchronous events. Simplest example may
> > by timeout (response to timer interrupt). Or we may wish
> > to change what the program is doing in response to external
> > event. At hardware level there are interrupt, at operating
> > system level we may get signals, so no problem at low level.
> > However, high-level language may have data structures with
> > non-trivial invariants. If we abort modification in the
> > middle data structures may be left in inconsistent state.
> > So, what is needed is transfer of control to handler at
> > next safepoint, that is at next place where program may be
> > safely interrupted. I assume that high-level language
> > compiler knows where safepoints are, so the only problem
> > is how to perform control transfer from safepoint to
> > handler. This is essentially what (in)famous "came from"
> > instruction is doing, but I am not aware of any real
> > hardware implementing "came from"...
> >
> > Possible solutions:
> >
> > 1) Set a flag in signal handler and check for the flag at
> > each safepoint. Low-level variant od this would keep
> > interrupts disabled most of the time and enable them
> > only at safepoints. This is problematic, because
> > checking inside tight loop may lead to significant
> > performance drop. Not checking inside loop may
> > lead to long delay before reaction to external signal.
> > Inserting checking code by hand could work, but is
> > error-prone and labor-intensive, so I want automatic
> > solution, that is compiler generated checks.
> > 2) Using debug registers: debug register causes transfer
> > to handler after arriving at designated address. This
> > is quite close to what "came from" should do and would
> > be a satisfactory solution. Unfortunately, debug
> > registers are not standard part of architecture and
> > access to debug registers may be restricted by operating
> > system.
> > 3) Separate cleanup routines: each instruction would have
> > associated cleanup routine which will continue computations
> > up to safepoint, but then transfer control to handler.
> > This may be quite satisfactory from performance point
> > of view, but require quite a lot of code.
> > 4) Modyfing code to replace instruction at safepoint
> > by jump. This has usual disadvantages of self-modyfying
> > code, but otherwise looks reasonable.
> > 5) Dynamicaly generating cleanup code: we could copy code
> > from current instruction pointer up to setpoint and add
> > jump to handler at the end. Assuming that code is position
> > independent this should work and is resonably simple. We
> > avoid modification of "normal code", but it is not clear
> > for me if modern CPU-s like it better than 4.
> > 6) Interpret machine instructions up to safepoint. Shuld work,
> > but is lot of code and potentialy slow.
> > 7) Modification of 3 and 6: generate cleanups as bytecode and
> > interpret it. IIUC this is essentially what DWARF is doing
> > to handle C++ exceptions. My impression is that this is
> > complicated to implement, requires a lot of code space and
> > is slow a runtime. OTOH less complicated than 6, probably
> > runs faster than 6 and needs less code space than 3.
> >
> > I wonder if there is other possible implementation that I
> > overlooked? And advantages/disadvantages that I overlooked?
> >
> Signals are obsolete long ago. Now use threads and implement
> user space scheduler.

Thread does not solve core problem here, only replace one
problem by different one: how to timely exchange information
between threads.

Threads would be attractive as they open possibilty to utilize
multiple cores, but they also open big can of worms. Namely,
I deal with "interesting" mutable data structures richly
interconnected via pointers. Tracking what is thread-local
and what is (potentially) shared looks like a nightmare.
Various languages tried to offer "safe" data structures
so that one can modify them from arbitrary thread. AFAICS
there is huge performace penalty and in many cases single
threaded program runs faster than multithread one, because
single thread does not pay synchronization costs needed
for safe multithreaded use. Silly but illustrative example
is C 'getchar()': when I benchmarked it thread-safe
'getchar()' it needed something like 500 clocks per characters,
while old classic getchar can be done in about 10 clocks
(or down to 2-3 instructions if compiler optimizations
work as intended).

--
Waldek Hebisch

Branimir Maksimovic <branimir.maksimovic@gmail.com> wrote:
> On 2021-07-30, Ivan Godard <ivan@millcomputing.com> wrote:
> > On 7/30/2021 2:47 PM, antispam@math.uni.wroc.pl wrote:
> >> This is more question of implementating high-level languages,
> >> but possible answers depend on computer architecture.
> >>
> >> Problem: We want to code in high-level language and we want
> >> to respond to asynchronous events. Simplest example may
> >> by timeout (response to timer interrupt). Or we may wish
> >> to change what the program is doing in response to external
> >> event. At hardware level there are interrupt, at operating
> >> system level we may get signals, so no problem at low level.
> >> However, high-level language may have data structures with
> >> non-trivial invariants. If we abort modification in the
> >> middle data structures may be left in inconsistent state.
> >> So, what is needed is transfer of control to handler at
> >> next safepoint, that is at next place where program may be
> >> safely interrupted. I assume that high-level language
> >> compiler knows where safepoints are, so the only problem
> >> is how to perform control transfer from safepoint to
> >> handler. This is essentially what (in)famous "came from"
> >> instruction is doing, but I am not aware of any real
> >> hardware implementing "came from"...
> >>
> >> Possible solutions:
> >>
> >> 1) Set a flag in signal handler and check for the flag at
> >> each safepoint. Low-level variant od this would keep
> >> interrupts disabled most of the time and enable them
> >> only at safepoints. This is problematic, because
> >> checking inside tight loop may lead to significant
> >> performance drop. Not checking inside loop may
> >> lead to long delay before reaction to external signal.
> >> Inserting checking code by hand could work, but is
> >> error-prone and labor-intensive, so I want automatic
> >> solution, that is compiler generated checks.
> >> 2) Using debug registers: debug register causes transfer
> >> to handler after arriving at designated address. This
> >> is quite close to what "came from" should do and would
> >> be a satisfactory solution. Unfortunately, debug
> >> registers are not standard part of architecture and
> >> access to debug registers may be restricted by operating
> >> system.
> >> 3) Separate cleanup routines: each instruction would have
> >> associated cleanup routine which will continue computations
> >> up to safepoint, but then transfer control to handler.
> >> This may be quite satisfactory from performance point
> >> of view, but require quite a lot of code.
> >> 4) Modyfing code to replace instruction at safepoint
> >> by jump. This has usual disadvantages of self-modyfying
> >> code, but otherwise looks reasonable.
> >> 5) Dynamicaly generating cleanup code: we could copy code
> >> from current instruction pointer up to setpoint and add
> >> jump to handler at the end. Assuming that code is position
> >> independent this should work and is resonably simple. We
> >> avoid modification of "normal code", but it is not clear
> >> for me if modern CPU-s like it better than 4.
> >> 6) Interpret machine instructions up to safepoint. Shuld work,
> >> but is lot of code and potentialy slow.
> >> 7) Modification of 3 and 6: generate cleanups as bytecode and
> >> interpret it. IIUC this is essentially what DWARF is doing
> >> to handle C++ exceptions. My impression is that this is
> >> complicated to implement, requires a lot of code space and
> >> is slow a runtime. OTOH less complicated than 6, probably
> >> runs faster than 6 and needs less code space than 3.
> >>
> >> I wonder if there is other possible implementation that I
> >> overlooked? And advantages/disadvantages that I overlooked?
> >>
> >
> > Simplest to implement would be to throw a C++ exception in the signal
> > handler and catch at the safepoint (catches are always safepoints in
> > C++). That lets C++ do the dwarfing instead of you.
> In signal handler you can't call printf let alone throw C++ exception :P

Well, from 'g++' help:

-fasynchronous-unwind-tables Generate unwind tables that are exact at each
instruction boundary.

What is intended use of this option?

--
Waldek Hebisch

On 2021-07-31, antispam@math.uni.wroc.pl <antispam@math.uni.wroc.pl> wrote:
> Branimir Maksimovic <branimir.maksimovic@gmail.com> wrote:
>> On 2021-07-30, antispam@math.uni.wroc.pl <antispam@math.uni.wroc.pl> wrote:
>> > This is more question of implementating high-level languages,
>> > but possible answers depend on computer architecture.
>> >
>> > Problem: We want to code in high-level language and we want
>> > to respond to asynchronous events. Simplest example may
>> > by timeout (response to timer interrupt). Or we may wish
>> > to change what the program is doing in response to external
>> > event. At hardware level there are interrupt, at operating
>> > system level we may get signals, so no problem at low level.
>> > However, high-level language may have data structures with
>> > non-trivial invariants. If we abort modification in the
>> > middle data structures may be left in inconsistent state.
>> > So, what is needed is transfer of control to handler at
>> > next safepoint, that is at next place where program may be
>> > safely interrupted. I assume that high-level language
>> > compiler knows where safepoints are, so the only problem
>> > is how to perform control transfer from safepoint to
>> > handler. This is essentially what (in)famous "came from"
>> > instruction is doing, but I am not aware of any real
>> > hardware implementing "came from"...
>> >
>> > Possible solutions:
>> >
>> > 1) Set a flag in signal handler and check for the flag at
>> > each safepoint. Low-level variant od this would keep
>> > interrupts disabled most of the time and enable them
>> > only at safepoints. This is problematic, because
>> > checking inside tight loop may lead to significant
>> > performance drop. Not checking inside loop may
>> > lead to long delay before reaction to external signal.
>> > Inserting checking code by hand could work, but is
>> > error-prone and labor-intensive, so I want automatic
>> > solution, that is compiler generated checks.
>> > 2) Using debug registers: debug register causes transfer
>> > to handler after arriving at designated address. This
>> > is quite close to what "came from" should do and would
>> > be a satisfactory solution. Unfortunately, debug
>> > registers are not standard part of architecture and
>> > access to debug registers may be restricted by operating
>> > system.
>> > 3) Separate cleanup routines: each instruction would have
>> > associated cleanup routine which will continue computations
>> > up to safepoint, but then transfer control to handler.
>> > This may be quite satisfactory from performance point
>> > of view, but require quite a lot of code.
>> > 4) Modyfing code to replace instruction at safepoint
>> > by jump. This has usual disadvantages of self-modyfying
>> > code, but otherwise looks reasonable.
>> > 5) Dynamicaly generating cleanup code: we could copy code
>> > from current instruction pointer up to setpoint and add
>> > jump to handler at the end. Assuming that code is position
>> > independent this should work and is resonably simple. We
>> > avoid modification of "normal code", but it is not clear
>> > for me if modern CPU-s like it better than 4.
>> > 6) Interpret machine instructions up to safepoint. Shuld work,
>> > but is lot of code and potentialy slow.
>> > 7) Modification of 3 and 6: generate cleanups as bytecode and
>> > interpret it. IIUC this is essentially what DWARF is doing
>> > to handle C++ exceptions. My impression is that this is
>> > complicated to implement, requires a lot of code space and
>> > is slow a runtime. OTOH less complicated than 6, probably
>> > runs faster than 6 and needs less code space than 3.
>> >
>> > I wonder if there is other possible implementation that I
>> > overlooked? And advantages/disadvantages that I overlooked?
>> >
>> Signals are obsolete long ago. Now use threads and implement
>> user space scheduler.
>
> Thread does not solve core problem here, only replace one
> problem by different one: how to timely exchange information
> between threads.
>
> Threads would be attractive as they open possibilty to utilize
> multiple cores, but they also open big can of worms. Namely,
> I deal with "interesting" mutable data structures richly
> interconnected via pointers. Tracking what is thread-local
> and what is (potentially) shared looks like a nightmare.
> Various languages tried to offer "safe" data structures
> so that one can modify them from arbitrary thread. AFAICS
> there is huge performace penalty and in many cases single
> threaded program runs faster than multithread one,
that is usually case with GC. forking is faster then using
threads. GC per process is faster then single GC per several
threads.

because
> single thread does not pay synchronization costs needed
> for safe multithreaded use.

ditto

Silly but illustrative example
> is C 'getchar()': when I benchmarked it thread-safe
> 'getchar()' it needed something like 500 clocks per characters,
> while old classic getchar can be done in about 10 clocks
> (or down to 2-3 instructions if compiler optimizations
> work as intended).

of course. single threaded getchar reads from stdio without
synchronization.
If you are concerned with thread performance try with forking?
Then, you don't need synchronization and can communicate by IPC.
Nowdays that is popular as they does all sort of things
to prevent threads to access shared mutable state.

>
>
Greetings, Branimir.

--
bmaxa now listens Ob-Neob Radio

On 2021-07-31, antispam@math.uni.wroc.pl <antispam@math.uni.wroc.pl> wrote:
> Branimir Maksimovic <branimir.maksimovic@gmail.com> wrote:
>> On 2021-07-30, Ivan Godard <ivan@millcomputing.com> wrote:
>> > On 7/30/2021 2:47 PM, antispam@math.uni.wroc.pl wrote:
>> >> This is more question of implementating high-level languages,
>> >> but possible answers depend on computer architecture.
>> >>
>> >> Problem: We want to code in high-level language and we want
>> >> to respond to asynchronous events. Simplest example may
>> >> by timeout (response to timer interrupt). Or we may wish
>> >> to change what the program is doing in response to external
>> >> event. At hardware level there are interrupt, at operating
>> >> system level we may get signals, so no problem at low level.
>> >> However, high-level language may have data structures with
>> >> non-trivial invariants. If we abort modification in the
>> >> middle data structures may be left in inconsistent state.
>> >> So, what is needed is transfer of control to handler at
>> >> next safepoint, that is at next place where program may be
>> >> safely interrupted. I assume that high-level language
>> >> compiler knows where safepoints are, so the only problem
>> >> is how to perform control transfer from safepoint to
>> >> handler. This is essentially what (in)famous "came from"
>> >> instruction is doing, but I am not aware of any real
>> >> hardware implementing "came from"...
>> >>
>> >> Possible solutions:
>> >>
>> >> 1) Set a flag in signal handler and check for the flag at
>> >> each safepoint. Low-level variant od this would keep
>> >> interrupts disabled most of the time and enable them
>> >> only at safepoints. This is problematic, because
>> >> checking inside tight loop may lead to significant
>> >> performance drop. Not checking inside loop may
>> >> lead to long delay before reaction to external signal.
>> >> Inserting checking code by hand could work, but is
>> >> error-prone and labor-intensive, so I want automatic
>> >> solution, that is compiler generated checks.
>> >> 2) Using debug registers: debug register causes transfer
>> >> to handler after arriving at designated address. This
>> >> is quite close to what "came from" should do and would
>> >> be a satisfactory solution. Unfortunately, debug
>> >> registers are not standard part of architecture and
>> >> access to debug registers may be restricted by operating
>> >> system.
>> >> 3) Separate cleanup routines: each instruction would have
>> >> associated cleanup routine which will continue computations
>> >> up to safepoint, but then transfer control to handler.
>> >> This may be quite satisfactory from performance point
>> >> of view, but require quite a lot of code.
>> >> 4) Modyfing code to replace instruction at safepoint
>> >> by jump. This has usual disadvantages of self-modyfying
>> >> code, but otherwise looks reasonable.
>> >> 5) Dynamicaly generating cleanup code: we could copy code
>> >> from current instruction pointer up to setpoint and add
>> >> jump to handler at the end. Assuming that code is position
>> >> independent this should work and is resonably simple. We
>> >> avoid modification of "normal code", but it is not clear
>> >> for me if modern CPU-s like it better than 4.
>> >> 6) Interpret machine instructions up to safepoint. Shuld work,
>> >> but is lot of code and potentialy slow.
>> >> 7) Modification of 3 and 6: generate cleanups as bytecode and
>> >> interpret it. IIUC this is essentially what DWARF is doing
>> >> to handle C++ exceptions. My impression is that this is
>> >> complicated to implement, requires a lot of code space and
>> >> is slow a runtime. OTOH less complicated than 6, probably
>> >> runs faster than 6 and needs less code space than 3.
>> >>
>> >> I wonder if there is other possible implementation that I
>> >> overlooked? And advantages/disadvantages that I overlooked?
>> >>
>> >
>> > Simplest to implement would be to throw a C++ exception in the signal
>> > handler and catch at the safepoint (catches are always safepoints in
>> > C++). That lets C++ do the dwarfing instead of you.
>> In signal handler you can't call printf let alone throw C++ exception :P
>
> Well, from 'g++' help:
>
> -fasynchronous-unwind-tables Generate unwind tables that are exact at each
> instruction boundary.
>
> What is intended use of this option?
>
intended use is that throwing exception from ordinary code will not
break if async signal happens. But, if you throw from signal handler
it will certainly break.

--
bmaxa now listens Ob-Neob Radio

On 2021-07-31, Branimir Maksimovic <branimir.maksimovic@gmail.com> wrote:
> On 2021-07-31, antispam@math.uni.wroc.pl <antispam@math.uni.wroc.pl> wrote:
>> Branimir Maksimovic <branimir.maksimovic@gmail.com> wrote:
>>> On 2021-07-30, Ivan Godard <ivan@millcomputing.com> wrote:
>>> > On 7/30/2021 2:47 PM, antispam@math.uni.wroc.pl wrote:
>>> >> This is more question of implementating high-level languages,
>>> >> but possible answers depend on computer architecture.
>>> >>
>>> >> Problem: We want to code in high-level language and we want
>>> >> to respond to asynchronous events. Simplest example may
>>> >> by timeout (response to timer interrupt). Or we may wish
>>> >> to change what the program is doing in response to external
>>> >> event. At hardware level there are interrupt, at operating
>>> >> system level we may get signals, so no problem at low level.
>>> >> However, high-level language may have data structures with
>>> >> non-trivial invariants. If we abort modification in the
>>> >> middle data structures may be left in inconsistent state.
>>> >> So, what is needed is transfer of control to handler at
>>> >> next safepoint, that is at next place where program may be
>>> >> safely interrupted. I assume that high-level language
>>> >> compiler knows where safepoints are, so the only problem
>>> >> is how to perform control transfer from safepoint to
>>> >> handler. This is essentially what (in)famous "came from"
>>> >> instruction is doing, but I am not aware of any real
>>> >> hardware implementing "came from"...
>>> >>
>>> >> Possible solutions:
>>> >>
>>> >> 1) Set a flag in signal handler and check for the flag at
>>> >> each safepoint. Low-level variant od this would keep
>>> >> interrupts disabled most of the time and enable them
>>> >> only at safepoints. This is problematic, because
>>> >> checking inside tight loop may lead to significant
>>> >> performance drop. Not checking inside loop may
>>> >> lead to long delay before reaction to external signal.
>>> >> Inserting checking code by hand could work, but is
>>> >> error-prone and labor-intensive, so I want automatic
>>> >> solution, that is compiler generated checks.
>>> >> 2) Using debug registers: debug register causes transfer
>>> >> to handler after arriving at designated address. This
>>> >> is quite close to what "came from" should do and would
>>> >> be a satisfactory solution. Unfortunately, debug
>>> >> registers are not standard part of architecture and
>>> >> access to debug registers may be restricted by operating
>>> >> system.
>>> >> 3) Separate cleanup routines: each instruction would have
>>> >> associated cleanup routine which will continue computations
>>> >> up to safepoint, but then transfer control to handler.
>>> >> This may be quite satisfactory from performance point
>>> >> of view, but require quite a lot of code.
>>> >> 4) Modyfing code to replace instruction at safepoint
>>> >> by jump. This has usual disadvantages of self-modyfying
>>> >> code, but otherwise looks reasonable.
>>> >> 5) Dynamicaly generating cleanup code: we could copy code
>>> >> from current instruction pointer up to setpoint and add
>>> >> jump to handler at the end. Assuming that code is position
>>> >> independent this should work and is resonably simple. We
>>> >> avoid modification of "normal code", but it is not clear
>>> >> for me if modern CPU-s like it better than 4.
>>> >> 6) Interpret machine instructions up to safepoint. Shuld work,
>>> >> but is lot of code and potentialy slow.
>>> >> 7) Modification of 3 and 6: generate cleanups as bytecode and
>>> >> interpret it. IIUC this is essentially what DWARF is doing
>>> >> to handle C++ exceptions. My impression is that this is
>>> >> complicated to implement, requires a lot of code space and
>>> >> is slow a runtime. OTOH less complicated than 6, probably
>>> >> runs faster than 6 and needs less code space than 3.
>>> >>
>>> >> I wonder if there is other possible implementation that I
>>> >> overlooked? And advantages/disadvantages that I overlooked?
>>> >>
>>> >
>>> > Simplest to implement would be to throw a C++ exception in the signal
>>> > handler and catch at the safepoint (catches are always safepoints in
>>> > C++). That lets C++ do the dwarfing instead of you.
>>> In signal handler you can't call printf let alone throw C++ exception :P
>>
>> Well, from 'g++' help:
>>
>> -fasynchronous-unwind-tables Generate unwind tables that are exact at each
>> instruction boundary.
>>
>> What is intended use of this option?
>>
> intended use is that throwing exception from ordinary code will not
> break if async signal happens. But, if you throw from signal handler
> it will certainly break.
>
>
Besides, throwing from C callback is no no, as Linux is written in C.

--
bmaxa now listens Ob-Neob Radio