Is an RTOS Required for Ada?

Is an RTOS Required for Ada?

[Tramse]

I have an application in which Ada95 is required.  The target microcontroller
is the Motorola 68336.  It a real simple application, it only needs to
read/write to fixed addresses (ports/data) and respond to a interupts.  We have
a real fast boot up requirement and small RAM resource (7.5K) and can't afford
the boot time and RAM requried for a RTOS.  

Can we use Ada and compile direct to 68K code without using an RTOS (like we
could in C)?

Mike

Re: Is an RTOS Required for Ada?

[Rakesh Malhotra]

Tramse wrote:
> 
> I have an application in which Ada95 is required.  The target microcontroller
> is the Motorola 68336.  It a real simple application, it only needs to
> read/write to fixed addresses (ports/data) and respond to a interupts.  We have
> a real fast boot up requirement and small RAM resource (7.5K) and can't afford
> the boot time and RAM requried for a RTOS.
> 
Yes you can certainly use Ada.  I have done so several times by
targetting the 68302, 68332, 68030 etc.

Regarding your point that you cannot afford the extra RAM required by an
RTOS or startup time - that is dependent on the compiler you use and
what features of Ada you want to use. 

e.g. On one project I worked on we used the Alsys (Ada83, company is now
called Aonix) compiler and a kernel called the SMART kernel.  If memory
serves me, the runtime portion (kernel + library) was only about 2KB or
2.5KB.   Everything on top of that was my application.   However, SMART
imposes many restrictions e.g. you cannot do tasking.  There are other
features of Ada that SMART will not allow you to have.    Also the
startup time is very fast - in msecs.
Alsys also comes with a full kernel but then that is a lot bigger and
also has higher latencies.

There are other Ada compilers also that have a no-RTOS option or minimal
RTOS option.  If your compiler has this then you are ok.   I think there
is a version of GNAT called GNORT - GNAT with no run-time.  I have also
used the Rational Verdix cross-compiler that had similar options.


> Can we use Ada and compile direct to 68K code without using an RTOS (like we
> could in C)?

Yes.

Rakesh

Re: Is an RTOS Required for Ada?

[Marin David Condic]

Tramse wrote:
> 
> I have an application in which Ada95 is required.  The target microcontroller
> is the Motorola 68336.  It a real simple application, it only needs to
> read/write to fixed addresses (ports/data) and respond to a interupts.  We have
> a real fast boot up requirement and small RAM resource (7.5K) and can't afford
> the boot time and RAM requried for a RTOS.
> 
> Can we use Ada and compile direct to 68K code without using an RTOS (like we
> could in C)?
> 
Its done all the time. However, you have to ask that question of your
particular compiler vendor. Just because it generates code for a 68336
(is there a compiler for this target?) doesn't mean it won't make code
that generates calls to some presumed OS. For example, GNAT will
generate calls to the OS to get tasking services done, but you can get
the RTEMS software which will provide for those primitives without the
presence of an OS (Unless you want to call RTEMS an OS. It may be more
accurate to describe it as a "Run Time Kernel" or "Run Time Support" -
not an RTOS - but lets not start that debate.) Some versions of GNAT
have the ability to generate "pure" code which makes no calls to any
runtime kernel (called GNORT), but naturally, you loose support for some
features. (I've never seriously looked into GNAT/RTEMS/GNORT because
I've never had an app where this seemed to be a fit. I can't tell you
how easy/hard it would be to use any of this.)

There are other vendors such as Aonix and Green Hills who have compilers
aimed at embedded targets and they probably have solutions as well.
There's nothing in Ada to prevent this - you just have to check how it
is done for the compiler/target combination.

Have you already acquired a compiler? If so, posting the brand & version
may help in getting more detailed information on how to go about doing
what you want to do.

MDC
-- 
Marin David Condic
Real Time & Embedded Systems, Propulsion Systems Analysis
United Technologies, Pratt & Whitney, Large Military Engines
M/S 731-95, P.O.B. 109600, West Palm Beach, FL, 33410-9600
***To reply, remove "bogon" from the domain name.***

Visit my web page at: http://www.flipag.net/mcondic

Re: Is an RTOS Required for Ada?

[Tramse]

>There are other Ada compilers also that have a no-RTOS option or minimal
>RTOS option.  If your compiler has this then you are ok.   I think there
>is a version of GNAT called GNORT - GNAT with no run-time.  I have also
>used the Rational Verdix cross-compiler that had similar options.

I've heard of GNAT, are their many users of GNORT?  Does anyone have experience
in running GNORT on Linux with a 68K target?  Are their any debugging tools?

Re: Is an RTOS Required for Ada?

[Robert Dewar]

In article <19990513150314.13727.00000147@ng-cs1.aol.com>,
  tramse@aol.com (Tramse) wrote:
> I have an application in which Ada95 is required.  The target
> microcontroller is the Motorola 68336.  It a real simple
> application, it only needs to read/write to fixed addresses
> (ports/data) and respond to a interupts.  We have
> a real fast boot up requirement and small RAM resource (7.5K)
> and can't afford the boot time and RAM requried for a RTOS.
>
> Can we use Ada and compile direct to 68K code without using an
> RTOS (like we could in C)?

Certainly using GNAT, the answer is yes. You simply restrict
your code so that it does not need RTOS services. The pragma
Restriction capability provides a nice way to control these
kind of restrictions so that the compiler enforces them.

You need not go as far as GNORT to achieve this, there are many
library routines which can be used perfectly fine in the kind
of environment you are envisioning. You will not have tasking
available, but you probably don't need it.

Alternatively, as one customer of ours has done, you can
implement your own tiny real time kernel to support the minimal
amount of services that GNAT requires for implementing a
restricted tasking capability corresponding to the Ravenscar
profile.


Robert Dewar
Ada Core Technologies


--== Sent via Deja.com http://www.deja.com/ ==--
---Share what you know. Learn what you don't.---

Re: Is an RTOS Required for Ada?

[Robert Dewar]

In article <19990514155120.03860.00000396@ng-cr1.aol.com>,
  tramse@aol.com (Tramse) wrote:
> I've heard of GNAT, are their many users of GNORT?  Does
> anyone have experience
> in running GNORT on Linux with a 68K target?  Are their any
> debugging tools?

Just to be clear. GNORT is only appropriate if you have a
safety-critical certification requirement. Otherwise there is
no need to exclude minimal run-time routines.

For example, in GNORT mode, the compiler will generate an open
loop for a block copy, to avoid calling the bcopy routine in
the run-time. Now of course this is a trivial routine, and in
a normal circumstance there is no reason not to include it. But
in a certified environment, you don't want even one byte of
non-certified code around, and GNORT meets this requirement
inexpensively and convincingly by having no bytes of run-time
code of any kind around.

But if you don't have a certification requirement, then there
are lots of routines in the library that can be freely used.
For example, there is no reason not to use the sorting routine
in the GNAT library, or the random number generator in the Ada
library, and there are literally hundreds of other library
run-time routines that may be perfectly appropriate to use in
the limited environment you have in mind without requiring
RTOS services. Basically the RTOS is required for I/O, Tasking,
and Interrupt services. If you avoid these requirements, you
do not need an RTOS.

Robert Dewar
Ada Core Technologies


--== Sent via Deja.com http://www.deja.com/ ==--
---Share what you know. Learn what you don't.---

Re: Is an RTOS Required for Ada?

[Robert A Duff]

Robert Dewar <dewar@gnat.com> writes:

> For example, in GNORT mode, the compiler will generate an open
> loop for a block copy, to avoid calling the bcopy routine in
> the run-time. Now of course this is a trivial routine, and in
> a normal circumstance there is no reason not to include it. But
> in a certified environment, you don't want even one byte of
> non-certified code around, and GNORT meets this requirement
> inexpensively and convincingly by having no bytes of run-time
> code of any kind around.

That makes no sense to me.  Why couldn't you just certify those run-time
routines that you use?  Isn't it easier to certify the bcopy routine,
than to certify many inlined copies of the same algorithm?

- Bob
-- 
Change robert to bob to get my real email address.  Sorry.

Re: Is an RTOS Required for Ada?

[Tarjei Tj�stheim Jensen]

Robert Dewar wrote
>For example, in GNORT mode, the compiler will generate an open
>loop for a block copy, to avoid calling the bcopy routine in
>the run-time


I'm rather surprised. I would assume that the most eficient way of doin this
would be to use inline assembly code. I thought most cpus have a nice set of
special instructions that will do this. Could there be problems with using
these instructions?


Greetings,

Re: Is an RTOS Required for Ada?

[Robert Dewar]

In article <wccogjh80os.fsf@world.std.com>,
  Robert A Duff <bobduff@world.std.com> wrote:
> Robert Dewar <dewar@gnat.com> writes:
>
> That makes no sense to me.  Why couldn't you just certify
> those run-time routines that you use?  Isn't it easier to
> certify the bcopy routine, than to certify many inlined copies
> of the same algorithm?

Well, certification issues often make no sense to technical
people not aware of the special requirements :-)

First of all, you cannot in general certify existing code,
because part of (at least some of the protocols) for
certification is to document (in exhausting and exhaustive)
detail, the procedures and protocols used to develop and
manage the code during the production process.

Certification is a very heavy and expensive process (I heard
one company quote an average productivity of one machine
instruction per day per person in this context).

You can get some idea of the expense of certifying a run-time
by looking at some of the products on the market today. They
are not inexpensive!

To reimplement under certification conditions, and to
actually certify even a small part of the run-time library
would be an expensive process that would have to be passed
on to the user. In the case of bcopy, as Tarjei points out,
the code is inline in most cases anyway. The added
certification of inlining the few cases that do not get
inlined in the normal case is negligible compared to the
cost of generating a special certified library.

Another issue is that there are several different protocols
for safety-critical certification. It is not possible to
provide a pre-certified run-time that adheres 100% too all
possible protocols, so one has to choose a commonly used
one. We find that many customers far prefer a model in which
they have custody over 100% of the code in the application,
and can make sure that all of the code meets their particular
certification requirements.

This is certainly a very specialized field, and we expect
the GNORT capability to be relevant only in those situations
where the 100% code certification issue is critical.

Robert Dewar
Ada Core Technologies


--== Sent via Deja.com http://www.deja.com/ ==--
---Share what you know. Learn what you don't.---

Re: Is an RTOS Required for Ada?

[Larry Kilgallen]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 769 bytes --]

In article <7i15hp$mc2@ftp.kvaerner.com>, "Tarjei Tj�stheim Jensen" <tarjei.jensen@kvaerner.no> writes:
> 
> Robert Dewar wrote
>>For example, in GNORT mode, the compiler will generate an open
>>loop for a block copy, to avoid calling the bcopy routine in
>>the run-time
> 
> 
> I'm rather surprised. I would assume that the most eficient way of doin this
> would be to use inline assembly code. I thought most cpus have a nice set of
> special instructions that will do this. Could there be problems with using
> these instructions?

Those with great concern for speed will often be using RISC machines,
where instruction sets have been simplified.  Presuming reasonable
caching inside the CPU, data loads and stores will dominate the
copy time.

Larry Kilgallen

Re: Is an RTOS Required for Ada?

[Tarjei Tj�stheim Jensen]

Larry Kilgallen wrote:

> Tarjei Tj�stheim Jensen writes:
> >
> > Robert Dewar wrote
> >>For example, in GNORT mode, the compiler will generate an open
> >>loop for a block copy, to avoid calling the bcopy routine in
> >>the run-time
> >
> >
> > I'm rather surprised. I would assume that the most eficient way of doin this
> > would be to use inline assembly code. I thought most cpus have a nice set of
> > special instructions that will do this. Could there be problems with using
> > these instructions?
>
> Those with great concern for speed will often be using RISC machines,
> where instruction sets have been simplified.  Presuming reasonable
> caching inside the CPU, data loads and stores will dominate the
> copy time.
>

My question was rather clumsily put: My surprise was that gnat used bcopy instead of generating the
instructions. It seems to be overkill to call a function instead of just emitting the assembly
instructions.

I seem to remember that function calls are supposed to eat clock cycles and should if possible be avoided.
Especially in cases like this where I assume (I've not checked this so I may be horribly wrong) this is a
frequent function call. It is hard to imagine the function call being any saving in either time or space
over emitting the code inline.


 Greetings,

Re: Is an RTOS Required for Ada?

[Larry Kilgallen]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1180 bytes --]

In article <3744657E.A04ABC52@online.no>, "Tarjei Tj�stheim Jensen" <tarjei@online.no> writes:

> I seem to remember that function calls are supposed to eat
> clock cycles and should if possible be avoided.
> Especially in cases like this where I assume (I've not
> checked this so I may be horribly wrong) this is a
> frequent function call. It is hard to imagine the function call
> being any saving in either time or space
> over emitting the code inline.

Some systems have tiered costs for function calls, depending
on the degree of complexity you require for the interface.

Certainly a function call can save space over a copy loop,
depending on not only the instruction set but also the rest
of the machine design (alignment, etc.)  Is saving space
worth it ?  Some compilers let you choose between saving
space and saving time.  For copying a long string, I would
think function call overhead would be lost in the noise.
For copying a short string, obviously not. Is the string
length known at compile time ?  I prefer to shy away from
criticizing a code generation algorithm until I have a
specific program of my own that gets bitten by a problem.

Larry Kilgallen

Re: Is an RTOS Required for Ada?

[Robert Dewar]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 543 bytes --]

In article <3744657E.A04ABC52@online.no>,
  "Tarjei Tj�stheim Jensen" <tarjei@online.no> wrote:
> I seem to remember that function calls are supposed to eat
> clock cycles and should if possible be avoided.

Things you "seem to remember" about all machines in general
are likely NOT to be true about all machines in general.
In particular, there are definitely architectures (e.g. Power)
where calls are cheap and indeed very often free.


--== Sent via Deja.com http://www.deja.com/ ==--
---Share what you know. Learn what you don't.---

Re: Is an RTOS Required for Ada?

[Robert Dewar]

In article <FCB3LD.2F2@sd.aonix.com>,
  "George Romanski" <romanski@aonix.com> wrote:
>
> If the compiler inserts code for you, then this inserted code
> must also be verified at level A.   (you will need
> requirements design, source code tests and all appropriate
> reviews)

Right! Of course the line between generating code for the source
you write, and "inserting code" is a very difficult, perhaps
impossible line to draw.

Let's take two extremes. The only inlining that goes on in GNORT
for example is very simple stuff. For example, if someone writes
a call to To_Address (XYZ) from System.Storage_Elements, then
this is inlined, but it also generates no code at all (it is
basically an unchecked conversion). There is no place in the
GNORT generated code where you see anything other than
straightforward code generation that corresponds exactly to
what you would expect from the source code.

Let's assume on the other hand that a GNORT like compiler
decides that it would be really nice to implement tasking.
It does it by including the entire code of the tasking run time
in your generated program. You can't simply decide that this
is inlining, though it could be technically achieved by
inlining. An attempt to say that this code did not need
independent certification would indeed be completely bogus
and would be considered cheating!

Drawing the precise line between these two extremes would not
be an easy task. In the case of GNORT itself, we keep the subset
so simple thatno such bogus insertions of code ever occur. You
don't typically want fancy language features anyway in a
safety-critical application!

Robert Dewar
Ada Core Technologies


--== Sent via Deja.com http://www.deja.com/ ==--
---Share what you know. Learn what you don't.---

Re: Is an RTOS Required for Ada?

[George Romanski]

Robert Dewar wrote in message <7i1b7p$3nb$1@nnrp1.deja.com>...
>In article <wccogjh80os.fsf@world.std.com>,
>  Robert A Duff <bobduff@world.std.com> wrote:
>> Robert Dewar <dewar@gnat.com> writes:
>>
>> That makes no sense to me.  Why couldn't you just certify
>> those run-time routines that you use?  Isn't it easier to
>> certify the bcopy routine, than to certify many inlined copies
>> of the same algorithm?
>
>Well, certification issues often make no sense to technical
>people not aware of the special requirements :-)
>
>First of all, you cannot in general certify existing code,
>because part of (at least some of the protocols) for
>certification is to document (in exhausting and exhaustive)
>detail, the procedures and protocols used to develop and
>manage the code during the production process.


Yes! most Safety Certification Standards require the process
used to develop and verify the safety critical software to be
recorded.  This forms an auditable trail which is checked by
the certification authorities or their representatives.

It is possible to 're-engineer' the process independently by
performing all of the required steps that were missed.
In general it is extremely hard for anyone to re-engineer
the requirements, design, hazard analysis and so on, for software
developed elsewhere. (e.g. by your compiler vendor)
>
>Certification is a very heavy and expensive process (I heard
>one company quote an average productivity of one machine
>instruction per day per person in this context).
>
>You can get some idea of the expense of certifying a run-time
>by looking at some of the products on the market today. They
>are not inexpensive!

Agreed!  at least 5 lines of test for every line of code.
I've seen 10 lines of test as well.
>
>To reimplement under certification conditions, and to
>actually certify even a small part of the run-time library
>would be an expensive process that would have to be passed
>on to the user. In the case of bcopy, as Tarjei points out,
>the code is inline in most cases anyway. The added
>certification of inlining the few cases that do not get
>inlined in the normal case is negligible compared to the
>cost of generating a special certified library.


Inlined code forms part of the operational software, it must
also be certified with the application.  The degree of rigor
depends on the standard and the criticality level.

At level A for DO-178B (the avionics standard) you have
several choices.

1) Implement your application using two or more different
    computers, different languages and different compilers.

    This allows you to show test coverage at the source code
    level.  An expensive process as the system must be
    developed independently, twice.

2) Show code coverage at the source code level, and
    show traceability between source and object code.

    This means analyzing your generated code to verify the paths
    introduced by the compiler. (a very time consuming and
    tedious process).  Perform coverage at the source code level.

3) Show code coverage at the machine code level.

Code coverage means showing decision, condition and the
"effectiveness" of conditions (MC/DC) - depending on
criticality levels.

If the compiler inserts code for you, then this inserted code
must also be verified at level A.   (you will need requirements
design, source code tests and all appropriate reviews)

At level B coverage need only be shown at the source code
level.   DO-178B is not explicit on this point and you could
use the compiler to hide library code so that you don't have
to produce certification materials for it.

The general feeling in the certification community is that this
would be cheating, and if the certification authorities found
out about this practice then the responsible "DER" (Designated
Engineering Representative) would have his signature
authority revoked.

This ambiguity in interpretation is being fixed.  Guidance
material is being produced to prevent  this source code level
trick to be used to hide any code.   If the compiler inserts
any code with decisions then evidence must be supplied
which shows all decisions being tested with both outcomes
and showing that the requirements for the inserted code are
satisfied.

When complete, the guidance materials will be published by
RTCA and EUROCAE and will be used as a supplement
to DO-178B.

>
>Another issue is that there are several different protocols
>for safety-critical certification. It is not possible to
>provide a pre-certified run-time that adheres 100% too all
>possible protocols, so one has to choose a commonly used
>one. We find that many customers far prefer a model in which
>they have custody over 100% of the code in the application,
>and can make sure that all of the code meets their particular
>certification requirements.

100% custody of the code is a requirement for certification but
so is the requirement for all of the additional materials needed.

>
>This is certainly a very specialized field, and we expect
>the GNORT capability to be relevant only in those situations
>where the 100% code certification issue is critical.
>
>Robert Dewar
>Ada Core Technologies
>
>
>--== Sent via Deja.com http://www.deja.com/ ==--
>---Share what you know. Learn what you don't.---

IT IS a specialized field, it requires a lot of discipline and effort
but must be taken very seriously - lives are at risk.

We have found that if certification evidence is produced under
DO-178B Level A,  then  a mapping document which traces
requirements of other standards into this evidence is acceptable.
e.g. Def-Stan 00-55, RIA-23, IEC-880 etc.

George Romanski
Director Safety critical Software
Aonix

Re: Is an RTOS Required for Ada?

[George Romanski]

Robert Dewar wrote in message <7ifapi$lf1$1@nnrp1.deja.com>...
>In article <FCB3LD.2F2@sd.aonix.com>,
>  "George Romanski" <romanski@aonix.com> wrote:
>>
>> If the compiler inserts code for you, then this inserted code
>> must also be verified at level A.   (you will need
>> requirements design, source code tests and all appropriate
>> reviews)
>
>Right! Of course the line between generating code for the source
>you write, and "inserting code" is a very difficult, perhaps
>impossible line to draw.


Agreed
>
>Let's take two extremes. The only inlining that goes on in GNORT
>for example is very simple stuff. For example, if someone writes
>a call to To_Address (XYZ) from System.Storage_Elements, then
>this is inlined, but it also generates no code at all (it is
>basically an unchecked conversion). There is no place in the
>GNORT generated code where you see anything other than
>straightforward code generation that corresponds exactly to
>what you would expect from the source code.

>
>Let's assume on the other hand that a GNORT like compiler
>decides that it would be really nice to implement tasking.
>It does it by including the entire code of the tasking run time
>in your generated program. You can't simply decide that this
>is inlining, though it could be technically achieved by
>inlining. An attempt to say that this code did not need
>independent certification would indeed be completely bogus
>and would be considered cheating!

Agreed
>
>Drawing the precise line between these two extremes would not
>be an easy task. In the case of GNORT itself, we keep the subset
>so simple thatno such bogus insertions of code ever occur. You
>don't typically want fancy language features anyway in a
>safety-critical application!

Let's take an array assignment as an example.
If the arrays do not overlap (slicing is forbidden) then a single decision
may be present (for the loop - assuming the loop is not unrolled)

Providing the assignment is completed the decision would have been
evaluated both true and false.

If the arrays overlap, then a decision may be required to decide
the direction of the indexing, and a decision for the loop.

If the array has a smaller component size than a normal addressed
memory unit (e.g. we can move a word quicker than 4 bytes) then the
loop may move words until it gets to the edges.  This will require
more decisions for the operation.

For Level B code, ALL decisions must be shown to have been taken
in both directions.  ( or the code must be identified and analysed
explicitly).  It may be hard  to write test conditions that evaluate all
inlined
decisions in both directions.

My personal view (there is majority, but no concensus on this at present) is
that
inserted code which includes decisions must be identified and verified, for
level B.  For level A multiple conditions would require additional
verification.

Inserted code that includes no branches will be verified with the
application itself, it must be shown that it has been executed, but
may not require specific tests.

If the language is so restricted that there are no branches in non-user
developed code ( the run-time system which includes code to initialise
the target processor, and any code generator suport routines) then
verification of the application becomes easier.  Of course this must
be balanced with the cost of the user having to write and verify more
code to compensate for the reduced functionality offered by the
subset.


>
>Robert Dewar
>Ada Core Technologies
>
>
>--== Sent via Deja.com http://www.deja.com/ ==--
>---Share what you know. Learn what you don't.---

Re: Is an RTOS Required for Ada?

[Robert Dewar]

In article <374EC6EA.61519FAF@praxis-cs.co.uk>,
  Rod Chapman <rod@praxis-cs.co.uk> wrote:
> Robert Dewar wrote:
> >
> My normal rule-of-thumb is "no surprises" - the compiler
> should not ever surprise me in its generated code, or (perhaps
> more simply put) generate code that I can't understand and
> map back to the source, irrespective of optimization

I don't think we can write into a standard that the code must
not surprise Rod Chapman :-)

Who knows what would surprise you.

Certainly if you know the Merced instruction set well, it would
surprise you NOT to see a simple if handled by predication (at
least it would surprise me). On this machine, that is the
natural way of handling things.

Obviously what one person expects and understands is going to
be quite different from what another person expects and
understands. The principle of "no optimization, no surprise"
is simply not one that can be given any formal definition.

Robert Dewar


Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.

Re: Is an RTOS Required for Ada?

[David C. Hoos, Sr.]

Richard D Riehle <laoXhai@ix.netcom.com> wrote in message
news:7in1km$90v@dfw-ixnews9.ix.netcom.com...
> In article <7imvsr$5bg$1@nnrp1.deja.com>,
> Robert Dewar <robert_dewar@my-deja.com> wrote:
<snip>
>  Somebody once suggested including a DWIM function in every
>  language.  Each potentially surprising construct could be
>  be coerced by the DWIM function.  DWIM is an acronym
>  for "Do what I mean!".
>
Well.. in the circles where I learned programming, that
instruction had a shorter mnemonic -- RPM (Read Programmer's Mind) ;)

Re: Is an RTOS Required for Ada?

[Robert Dewar]

In article <FCCLAJ.Esq@sd.aonix.com>,
  "George Romanski" <romanski@aonix.com> wrote:

> My personal view (there is majority, but no concensus on this
> at present) is that inserted code which includes decisions
> must be identified and verified, for level B.

That seems a reasonable working approximation. Certainly GNAT
does not begin to come close to this line (really it does not
do much insertion in this sense at all, and certainly nothing
that involves complex decisions, I agree with George that this
would usually cross the line).

But the line is still murky.

After all, what if the decision was not generated by inserting
code, but directly by the compiler's code generator. In this
case there *is* no source code to identify in this case, but
certainly you have to check all paths if your certification
discipline involves this. A lot of directly generated code
involves such decisions. As an example, consider:

   A,B,C : Integer;
   A := B / C;

on the 8086. You cannot simply generate a DIV instruction
since there is a bug which causes 16#8000# (largest negative
number) / 1 to divide trap. So either this has to be fixed
up in the divide trap handler, or you have to check this case
specially, generating a decision point in the code.

Second, especially in modern predicated architectures,
conditional jumps tend to disappear anyway as a result of
if conversions. Should there be a principle that every
predicated instruction must be executed with and without
the predicate being True. Sounds reasonable, but I don't
know if testing standards have caught up with this.

Third, there are lots of cases that involve no predication,
and no explicit testing, but they do strange things to avoid
jumps. For example, consider the following computation of
MAX (EAX, EBX) on a 386:

                     -- EAX < EBX   EAX >= EBX

    CMP   EAX. EBX   -- CF = 1        CF = 0
    SBB   EDX, EDX   -- all 1 bits    all 0 bits
    MOV   ECX, EDX
    NOT   ECX        -- all 0 bits    all 1 bits
    AND   EDX, EBX   --   EBX            0
    AND   ECX, EAX   --    0            EAX
    OR    EDX, ECX   --    MAX (EAX, EBX)

No predication, no jumps, but one would sure like to check
this code in "both directions", yet this is not easy to codify
either in terms of directly generated code or in terms of
inlined inserted code.

Note that a clever compiler might generate the above sequence
from code that looked like:

      if A >= B then
         C := A;
      else
         C := B;
      end if;

so a decision point in the source has disappeared in the
generated code. Of course if the source code had written
MAX, then we don't have an obvious decision point in the
source, but depending on the machine we might see:

   1. A single MAX instruction (Power)
   2. The above hairy sequence (x86)
   3. A converted if, using predication, with no jumps (Merced)
   4. An explicit test and jumps (Sparc)

So decision points in the source may not correspond to decision
points in the object in any obvious way.

I give this example just to remind us that, unlike the
formalists view of precise mathematical verification, the
real world of safety-critical verification is a more pragmatic
one. The FAA rules (and other similar verification protocols)
do not guarantee 100% correctness in a formal sense, but they
have been found to be effective in practice, and we refine the
practice based on experience as we go along.

That there is not yet a consensus on some of these issues is
not surprising, this is a very tricky area, and one in which
common sense is not necesarily the best guide :-)


Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.

Re: Is an RTOS Required for Ada?

[Richard D Riehle]

In article <7imvsr$5bg$1@nnrp1.deja.com>,
	Robert Dewar <robert_dewar@my-deja.com> wrote:

>In article <374EC6EA.61519FAF@praxis-cs.co.uk>,
>  Rod Chapman <rod@praxis-cs.co.uk> wrote:
>> Robert Dewar wrote:
>> >
>> My normal rule-of-thumb is "no surprises" 
>
>I don't think we can write into a standard that the code must
>not surprise Rod Chapman :-)
>
 Somebody once suggested including a DWIM function in every
 language.  Each potentially surprising construct could be
 be coerced by the DWIM function.  DWIM is an acronym
 for "Do what I mean!".  

 Richard Riehle
 richard@adaworks.com
 http://www.adaworks.com

Re: Is an RTOS Required for Ada?

[Rod Chapman]

Robert Dewar wrote:
> 
> Right! Of course the line between generating code for the source
> you write, and "inserting code" is a very difficult, perhaps
> impossible line to draw.

My normal rule-of-thumb is "no surprises" - the compiler should
not ever surprise me in its generated code, or (perhaps
more simply put) generate code that I can't understand and
map back to the source, irrespective of optimization
level.  I'm quite happy to accept simple inlined loops
for block assignment or comparison, since these seem perfectly
reasonable, whether as a result of inlining or not.

Just me penneth worth...
 - Rod

Re: Is an RTOS Required for Ada?

[Robert A Duff]

The question was why is a no-run-time-system implementation of Ada
better for safety-critical applications.  I don't think Robert Dewar and
George Romanski have answered it in the technical sense.  They both
seemed to be saying, "because the standards say so".  Well, that's a
reason, but it's not a *technical* reasion.

"George Romanski" <romanski@aonix.com> writes:
> Let's take an array assignment as an example.
> If the arrays do not overlap (slicing is forbidden) then a single decision
> may be present (for the loop - assuming the loop is not unrolled)
> 
> Providing the assignment is completed the decision would have been
> evaluated both true and false.
> 
> If the arrays overlap, then a decision may be required to decide
> the direction of the indexing, and a decision for the loop.
> 
> If the array has a smaller component size than a normal addressed
> memory unit (e.g. we can move a word quicker than 4 bytes) then the
> loop may move words until it gets to the edges.  This will require
> more decisions for the operation.
> 
> For Level B code, ALL decisions must be shown to have been taken
> in both directions.  ( or the code must be identified and analysed
> explicitly).  It may be hard  to write test conditions that evaluate all
> inlined
> decisions in both directions.

Fine -- we both agree that the more complicated the code is, the harder
it is to test and verify.  But I don't see how putting any of the above
array-assignment algorithms in a run-time system, as opposed to
generated code, makes things worse.  If anything, it should make things
easier, because there's only one copy of that algorithm to verify
(recall Robert's 1 machine instruction per day metric).

> My personal view (there is majority, but no concensus on this at present) is
> that
> inserted code which includes decisions must be identified and verified, for
> level B.  For level A multiple conditions would require additional
> verification.
> 
> Inserted code that includes no branches will be verified with the
> application itself, it must be shown that it has been executed, but
> may not require specific tests.

I'm not sure what you mean by "inserted code".  Is it any different than
"generated code"?  Does it make any difference to what extent the
compiler is table driven?  I don't see why it should.

In any case, it seems to me that OF COURSE you have to verify all the
code in a safety-critical application -- and that OF COURSE includes
code from a run-time system, if any.  And you have to do your analysis
at the machine code level, because you don't trust the compiler.

- Bob
-- 
Change robert to bob to get my real email address.  Sorry.

Re: Is an RTOS Required for Ada?

[Robert Dewar]

In article <wccn1y9i9f2.fsf@world.std.com>,
  Robert A Duff <bobduff@world.std.com> wrote:

> The question was why is a no-run-time-system implementation of
> Ada better for safety-critical applications.  I don't think
> Robert Dewar and George Romanski have answered it in the
> technical sense.  They both seemed to be saying, "because the
> standards say so".  Well, that's a reason, but it's not a
> *technical* reasion.

The point is that safety-critical systems must be certified.
Certification implies many things.

No one said that a no-run-time system is better for SC
applications, and I seriously doubt George would agree,
seing as Aonix is in the business of selling certified
runtimes for this purpose!

The point is that given the certification requirement, the
no-run-time approach is a practical one for meeting the
requirements in a cost effective manner. Notice I say "a"
practical one, not "the only" practical one.

I think Bob is confused into thinking that the only requirement
for an SC system is that it work reliably. Well that is not the
case, it has to be SEEN and BELIEVED to work reliably by those
who acquire it, and it is for this that certification is
required.

Sure, you can take issue with the particular requirements of
certification if you like (although you need to know quite a bit
about the field to do so in an informed manner), but given the
current certification requirements, and in particular the fact
that you cannot certify code after the fact, this approach makes
sense.

Is this a technical requirement? I am not quite sure what that
means. Given that the specification *requires* certification
according to a standard, I would say that it is indeed a
technical requirement that any implementation approach adhere to
these certification requirements.

If for you technical is narrowly restricted to the idea of
code and whether it works or not, that is simply far too
restricted a notion to be useful in a safety critical
context.




Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.