$0.03 microcontroller

On 17/10/18 09:03, Hans-Bernhard Bröker wrote:
> Am 16.10.2018 um 23:01 schrieb gnuarm.deletethisbit@gmail.com:
> Reentrance is a problem any time a
>> routine is entered again before it is exited from a prior call.  This
>> can happen without multiple threads when a routine is called from a
>> routine that was ultimately called from within the routine.  I
>> suppose you might consider this to be recursion,
> Oh, there's no doubt about it: that's recursion all right.
> Some might prefer to qualify it as indirect recursion, a.k.a. a loop in
> the call graph, but it's still recursion.
We call it mutual recursion.

On Tuesday, October 16, 2018 at 6:03:55 PM UTC-4, Hans-Bernhard Bröker wrote:
> Am 16.10.2018 um 23:01 schrieb gnuarm.deletethisbit@gmail.com:
> > On Tuesday, October 16, 2018 at 4:52:44 PM UTC-4, Hans-Bernhard
> > Bröker wrote:
> 
> >> OTOH, one does tend to influence the other.  Without recursion,
> >> one would only really need reentrance to be able to call the same
> >> function from separate threads of execution.  On controllers this
> >> small, that would only happen if you're calling the same function
> >> from inside an interrupt handler and the main loop.
> 
> > I don't believe this is correct.  Reentrance is a problem any time a
> > routine is entered again before it is exited from a prior call.  This
> > can happen without multiple threads when a routine is called from a
> > routine that was ultimately called from within the routine.  I
> > suppose you might consider this to be recursion, 
> 
> Oh, there's no doubt about it: that's recursion all right.
> 
> Some might prefer to qualify it as indirect recursion, a.k.a. a loop in
> the call graph, but it's still recursion.
> 
> > but my point is this
> > can happen without the intent of using recursion.
> 
> I'll asume we agree on this: unintended recursion is clear a bug in the
> code, every time.

Clearly there would be a bug, but it is just as much that the routine wasn't designed for recursion and that would be the most likely fix. 


> That could arguably be classified an actual benefit of using a such a
> stack-starved CPU architecture: any competent C compiler for it will
> have to perform call tree analysis anyway, so it finds that particular
> bug "en passant".

Are you swearing at me in French?  ;)  


> More typical C toolchains relying on stack-centric calling conventions
> might not bother with such analysis, and thus won't see the bug.  Until
> you use the accompanying stack size calculation tool, that is, which
> will barf.

Yeah, I'm not much of a C programmer, so I wouldn't know about such tools.  What made me think of this is a problem often encountered by novices in Forth.  Some system words use globally static data and can be called twice from different code before the first call has ended use of the data structure.  Not quite the same thing as recursion, but the same result. 

Rick C.

On 17/10/2018 00:03, Hans-Bernhard Bröker wrote:

> I'll asume we agree on this: unintended recursion is clear a bug in the
> code, every time.

I think we can agree that /any/ unintended action is a clear bug in the 
code!

But recursion or re-entrancy without a clear purpose and careful limits 
on depths is a bug in the /design/, not just the code.

When I am faced with someone else's code to examine or maintain, I often 
run it through Doxygen with "generate documentation for /everything/ - 
caller graphs, callee graphs, cross-linked source, etc."  It can make it 
quick to jump around in the code.  And recursive (or re-entrant, 
whichever you prefer) code stands out like a sore thumb, as long as the 
code is single-threaded - you get loops in the call graphs.

The only other case is if interrupts call other functions - that won't 
be seen so easily.

Am 16.10.2018 um 22:52 schrieb Hans-Bernhard Bröker:
> 
>  Without recursion, one
> would only really need reentrance to be able to call the same function
> from separate threads of execution.  On controllers this small, that
> would only happen if you're calling the same function from inside an
> interrupt handler and the main loop.  And frankly: you really don't want
> to do that.  If an ISR on this kind of hardware becomes big enough you
> feel the need to split it into sub-functions, that almost certainly
> means you've picked entirely the wrong tool for the job.
> 
> In other words: for this kind of system (very small, with rotten
> stack-based addressing), not only doesn't everyone need re-entrant
> functions, it's more like nobody does.

Multithreading matters here. It is not common on such small devices, but
this one is an exception: Padauk sells multiple dual-core variants of
this controller and one 8-core variant.
And there is always the support functions the compilers tend to need on
small systems (while I assume people would think twice before using an
expensive division in an interrupt handler, the situation looks
different for multithreading).

> 
> I don't think anyone has ever seriously claimed SDCC to be anywhere near
> the pinnacle of compiler design for the 8051.  ;-P
> 
> Frankly, just looking at statements in this thread has me thinking that
> the usual suspects among commercial offerings from 20 years ago might
> still run circles around it today.

I don't know of a current comparison for the MCS-51.

For MCS-51, I do not know of a good compiler comparison; I did some
benchmarks a while ago
(https://sourceforge.net/p/sdcc/mailman/message/36359114/), and SDCC
still has a bit of catching-up to do.

On the other hand, for the STM8, SDCC seems to be doing more than just
okay: http://www.colecovision.eu/stm8/compilers.shtml

Philipp

On 18-10-17 01:46 , David Brown wrote:
  ...
> When I am faced with someone else's code to examine or maintain, I often
> run it through Doxygen with "generate documentation for /everything/ -
> caller graphs, callee graphs, cross-linked source, etc."  It can make it
> quick to jump around in the code.  And recursive (or re-entrant,
> whichever you prefer) code stands out like a sore thumb, as long as the
> code is single-threaded - you get loops in the call graphs.

Anecdote: some years ago, when I was applying a WCET analysis tool to 
someone else's program, the tool found recursion. This surprised the 
people I was working with, because they had generated call graphs for 
the program, analysed them visually, and found no recursive, looping paths.

Turned out that they had asked the call-graph tool to optimize the size 
of the window used to display the call-graphs. The tool did as it was 
told, with the result that the line segments on the path for the 
recursive call went down to the bottom edge of the diagram, then 
*merged* with the lower border line of the diagram, followed that lower 
border, went up one side of the diagram -- still merged with the border 
line -- and then reentered the diagram to point at the source of the 
recursive call, effectively making the loop very hard to see...

(It turned out that this recursion was intentional. At this point, the 
program was sending an alarm message, but the alarm buffer was full, so 
the alarm routine called itself to send an alarm about the full buffer 
-- and that worked, because one buffer slot was reserved, by design, for 
this "buffer full" alarm.)

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .

On 17/10/18 08:35, Niklas Holsti wrote:
> On 18-10-17 01:46 , David Brown wrote:
>  ...
>> When I am faced with someone else's code to examine or maintain, I often
>> run it through Doxygen with "generate documentation for /everything/ -
>> caller graphs, callee graphs, cross-linked source, etc."  It can make it
>> quick to jump around in the code.  And recursive (or re-entrant,
>> whichever you prefer) code stands out like a sore thumb, as long as the
>> code is single-threaded - you get loops in the call graphs.
> 
> Anecdote: some years ago, when I was applying a WCET analysis tool to
> someone else's program, the tool found recursion. This surprised the
> people I was working with, because they had generated call graphs for
> the program, analysed them visually, and found no recursive, looping paths.
> 
> Turned out that they had asked the call-graph tool to optimize the size
> of the window used to display the call-graphs. The tool did as it was
> told, with the result that the line segments on the path for the
> recursive call went down to the bottom edge of the diagram, then
> *merged* with the lower border line of the diagram, followed that lower
> border, went up one side of the diagram -- still merged with the border
> line -- and then reentered the diagram to point at the source of the
> recursive call, effectively making the loop very hard to see...

Visual tools are helpful, but don't show everything!

On the other hand, they can show things that can be hard to quantify in
more rigorous tools.  It is easy to look at the call graph of a function
and say "that function is a bowl of spaghetti, and needs restructured" -
it's harder to define rules or limits for an automatic checker that make
such judgements.

> 
> (It turned out that this recursion was intentional. At this point, the
> program was sending an alarm message, but the alarm buffer was full, so
> the alarm routine called itself to send an alarm about the full buffer
> -- and that worked, because one buffer slot was reserved, by design, for
> this "buffer full" alarm.)
> 

I can appreciate the purpose here, but I would rather have this:

static bool putAlarmInLog(alarmPtr slot, ...) { ... }

static alarmSlot_t alarmSlots[maxAlarmSlots];
static alarmSlot_t emergencyAlarmSlot;

static alarmPtr findFreeAlarmSlot(void) { ... }

void logAlarm(...) {
	alarmPtr = findFreeAlarmSlot();
	if (alarmPtr) {
		putAlarmInLog(alarmPtr, ...);
	} else {
		putAlarmInLog(&emergencyAlarmSlot, "Buffer full");
	}
}


Hoist the condition checks up a step, and put the actual storage
mechanism down a step, and you no longer have the re-entrancy.  The code
is a lot easier to write, read, analyse and test.

On Wednesday, October 17, 2018 at 2:35:46 AM UTC-4, Niklas Holsti wrote:
> On 18-10-17 01:46 , David Brown wrote:
>   ...
> > When I am faced with someone else's code to examine or maintain, I often
> > run it through Doxygen with "generate documentation for /everything/ -
> > caller graphs, callee graphs, cross-linked source, etc."  It can make it
> > quick to jump around in the code.  And recursive (or re-entrant,
> > whichever you prefer) code stands out like a sore thumb, as long as the
> > code is single-threaded - you get loops in the call graphs.
> 
> Anecdote: some years ago, when I was applying a WCET analysis tool to 
> someone else's program, the tool found recursion. This surprised the 
> people I was working with, because they had generated call graphs for 
> the program, analysed them visually, and found no recursive, looping paths.
> 
> Turned out that they had asked the call-graph tool to optimize the size 
> of the window used to display the call-graphs. The tool did as it was 
> told, with the result that the line segments on the path for the 
> recursive call went down to the bottom edge of the diagram, then 
> *merged* with the lower border line of the diagram, followed that lower 
> border, went up one side of the diagram -- still merged with the border 
> line -- and then reentered the diagram to point at the source of the 
> recursive call, effectively making the loop very hard to see...
> 
> (It turned out that this recursion was intentional. At this point, the 
> program was sending an alarm message, but the alarm buffer was full, so 
> the alarm routine called itself to send an alarm about the full buffer 
> -- and that worked, because one buffer slot was reserved, by design, for 
> this "buffer full" alarm.)

Seems to me what actually failed was that they knew they had recursion in the design but didn't realize the fact that they didn't see the recursion in the call graphs was an error that should have been caught. 

Rick C. 

On Tue, 16 Oct 2018 22:52:37 +0200, Hans-Bernhard Bröker
<HBBroeker@t-online.de> wrote:

>The major part of it is that I mixed up Reentrance with Recursion there
>... sorry for that.
>
>OTOH, one does tend to influence the other.  Without recursion, one
>would only really need reentrance to be able to call the same function
>from separate threads of execution. 

Recursion simply is a particlar useage of re-entrance: a function
calling itself (possibly indirectly through other functions).

You can use re-entrant functions without using recursion, but you
can't recurse without re-entrant functions.


Of course, re-entrance doesn't depend on a CPU stack ... it requires
only that the local variables of each instance be kept separate.  That
can be done with auxiliary data structures.
[It's interesting to watch programming students reinvent recursion -
accidentally, or as an exercise - and realize all the effort saved by
having it built into the language.]

George

On 18-10-17 17:08 , gnuarm.deletethisbit@gmail.com wrote:
> On Wednesday, October 17, 2018 at 2:35:46 AM UTC-4, Niklas Holsti
> wrote:
>> On 18-10-17 01:46 , David Brown wrote: ...
>>> When I am faced with someone else's code to examine or maintain,
>>> I often run it through Doxygen with "generate documentation for
>>> /everything/ - caller graphs, callee graphs, cross-linked source,
>>> etc."  It can make it quick to jump around in the code.  And
>>> recursive (or re-entrant, whichever you prefer) code stands out
>>> like a sore thumb, as long as the code is single-threaded - you
>>> get loops in the call graphs.
>>
>> Anecdote: some years ago, when I was applying a WCET analysis tool
>> to someone else's program, the tool found recursion. This surprised
>> the people I was working with, because they had generated call
>> graphs for the program, analysed them visually, and found no
>> recursive, looping paths.
>>
>> Turned out that they had asked the call-graph tool to optimize the
>> size of the window used to display the call-graphs. The tool did as
>> it was told, with the result that the line segments on the path for
>> the recursive call went down to the bottom edge of the diagram,
>> then *merged* with the lower border line of the diagram, followed
>> that lower border, went up one side of the diagram -- still merged
>> with the border line -- and then reentered the diagram to point at
>> the source of the recursive call, effectively making the loop very
>> hard to see...
>>
>> (It turned out that this recursion was intentional. At this point,
>> the program was sending an alarm message, but the alarm buffer was
>> full, so the alarm routine called itself to send an alarm about the
>> full buffer -- and that worked, because one buffer slot was
>> reserved, by design, for this "buffer full" alarm.)
>
> Seems to me what actually failed was that they knew they had
> recursion in the design but didn't realize the fact that they didn't
> see the recursion in the call graphs was an error that should have
> been caught.

The guys creating and viewing the call-graphs were not the designers of 
the program, either, so they didn't know, but for sure it was something 
they should have discovered and remarked on as part of their work.

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .

On Wed, 17 Oct 2018 08:23:57 +0200, Philipp Klaus Krause <pkk@spth.de>
wrote:

>Am 16.10.2018 um 22:52 schrieb Hans-Bernhard Br&#4294967295;ker:
>> 
>>  Without recursion, one
>> would only really need reentrance to be able to call the same function
>> from separate threads of execution.  On controllers this small, that
>> would only happen if you're calling the same function from inside an
>> interrupt handler and the main loop.  And frankly: you really don't want
>> to do that.  If an ISR on this kind of hardware becomes big enough you
>> feel the need to split it into sub-functions, that almost certainly
>> means you've picked entirely the wrong tool for the job.
>> 
>> In other words: for this kind of system (very small, with rotten
>> stack-based addressing), not only doesn't everyone need re-entrant
>> functions, it's more like nobody does.
>
>Multithreading matters here. It is not common on such small devices, but
>this one is an exception: Padauk sells multiple dual-core variants of
>this controller and one 8-core variant.

While I have been playing around with the idea of making some RTOS for
such 1kW/64B machine (realistically supporting 2-3 tasks such as a
foregroud/bacground monitor)  realistically having 2 or 8 thread is no
very realistic, even if the hardware supports it.

The 8 core version might be usable for xCore style "pseudo-interupts"
running a single DSP sample or PLC loop at a time. This would require
8 input pins, each starting its own thread. 

But of course, the same rules should apply to pseudo-interrupts as
real interrupts regarding re-entrancy etc.