Re: Beware: Rep spec on an enumeration type causes code explosion

[gwinn@res.ray.com (Joe Gwinn)]

In article <34989D6B.402AE2A7@ac3i.dseg.ti.com>, johnv@ac3i.dseg.ti.com wrote:

> Joe Gwinn wrote:
> > 
> > In article <3496D55F.1312429E@ac3i.dseg.ti.com>,
johnv@ac3i.dseg.ti.com wrote:
> > 
> > > I don't see how this requirement conflicts with the idiom I sketched
> > > before (derive a "holey" enumeration type from a parent "contiguous"
> > > enumeration type, and rely on Ada type conversions to provide the
> > > necessary mapping).  Your program only needs to deal with these "secure"
> > > but "holey" message id bit patterns at its edges, where it receives and
> > > unpacks input messages (whose provenance may be questionable) and where
> > > it must pack up and transmit output messages (and establish their
> > > provenance)...[snip]
> > 
> > Well, it depends on where one chooses to put the boundaries between safe
> > and unsafe.  Because we choose not to attempt safety validation of VxWorks
> > and the various COTS communications systems, an impossible task, every
> > VxWorks task stands alone, so safety critical messages between tasks must
> > have message type IDs differing in at least 4 bits.  I think this meets
> > the definition of holey; in fact, it's more hole than anything else, by
> > design.
> > 
> > So, can one convert to a compact enumeration within those tasks, defining
> > the "edges" to be the task boundaries?  
> 
> Sure, why not?
> 
> > Not really, both by common sense
> 
> "Common sense"?  If common sense has anything to do with this, I'm
> afraid you aren't very convincing in showing the connection...

The common sense is that nothing has divine protection, as discussed later
in the original posting.


> > and by a specific contractual safety requirement.  Enumeration types
> > within the task are still implemented using physical memory, there being
> > no other way, and thus have no more divine protection from bitflips and
> > other forms of spoofing then they do outside the tasks.
> 
> There must be some limit to this paranoia, else we degenerate into
> infinite regress!  I can understand being paranoid about flipped bits in
> messages coming in over a network connection, where the communication
> line may be held suspect, but to worry about a bit flipping in a
> variable in memory while it is being used within a single task on a
> single host processor is surely beyond the pale.  

The greatest fear is that some other bit of software will scribble on our
precious data structures.  This applies across the board, not just to
messages.  And, in some applications, bitflips are physically possible, a
consequence of using semiconductor RAM, which can have bits flipped by
stray cosmic rays and alpha particles from the ceramic used to make the IC
package.  In satellites, there is plenty of natural radiation, so bitflips
(and worse) are actually fairly common.


> ... One may as well outlaw
> the use of standard 2's-complement integers and floats for representing
> critical physical quantities, on the grounds that a single bit flip
> could suddenly double a quantity, or worse yet, change its sign! 

I hate to tell you this, but in some applications we do exactly this, as a
guard against (transient) errors in the CPU's arithmetic logic.  No
hardware is perfect.  Actually, we do all arithmetic twice in the same CPU
but by somewhat different mathematical paths, and compare the results. 
Paranoia is proportional to the product of risk and consequence.


> ... We
> would also have to preclude the use of standard CPU models with
> instruction sets that aren't sufficiently "holey", on the grounds that a
> single bit flip could suddently turn, say, a LOAD instruction into a
> STORE instruction!

We haven't gone quite that far; the parallel paths and compare is
sufficient, and standard hardware is so much cheaper than special
hardwware that we would instead use multiple CPUs in lockstep and compare
their outputs.  This is called triple modular redundancy, and is widely
used in fly-by-wire systems, for instance.

It all depends on what threats one is countering.


> Even putting that aside, let's asume that there is some compelling
> reason to keep using a "holey" representation even within a single task
> (and let's also assume that your comments are not simply a troll). Then,
> as you say:
> 
> [snip, fast-forward to the end]
> 
> > The
> > holes are absolutely required and thus will remain.  Something else will
> > be forced to give.
> 
> ... Of course: You must give up some efficiency.  If one cannot trust an
> enumerated value to remain intact from one executable statement to the
> next, then one is forced to constantly check and re-check it to make
> sure it hasn't gone bad.  Each iteration through a for-loop, each index
> into an array, and so forth, must pay the cost of mapping the
> representation to the position number (raising Constraint_Error if the
> represented value is not 'Valid). In short, you incur the "blow up"
> which you previously complained about.  You cannot have it both ways:
> You can get speed or you can get safety, but not both at once.

Yes, it's more costly to support a sparse enumeration mapping, but I don't
think that it needs to be a factor of 100 to 1000 more expensive.  At
worst, one could use a standard-issue hash table to hold the mapping
pairs; this approach has constant overhead regardless of the nature of the
holes, and could be less than 10 times more expensive.

Also, we have drifted off the point a bit.  The reason for the rep specs
on an enumeration type was to permit interchange of data between systems
not all in the same language or even compiler; the bits must be pinned
down or every time somebody gets a new version, the system will collapse. 
The presence or absence of holes in the enumeration, though important, is
an independent issue.

 
> At any rate, what does this have to say about the suitability of an Ada
> enumeration type as an abstraction for a "holey" set of bit-patterns? 
> If you choose some other data abstraction to implement the bit-patterns,
> you will get the same sort of performance, but you will have to do some
> programming work to implement the very same mapping operations that the
> Ada compiler already provides for a holey enumeration type. Seems like
> wrong-headedness leading to wasted effort...

I don't agree.  Users have an intrinsic advantage over compiler writers in
that users know just what they are trying to do, and so can build a
mechanism that answers that need and that need alone, while compiler
writers are forced to cover entire spaces of possible needs.  

Specifically, we can implement the hash table ourselves, or even choose to
spend lots of memory on a large but mostly empty lookup table.  Compiler
writers cannot use such limited solutions because they are pulled too many
ways by too many users.

For the record, I once ran an 6-person compiler group whose main mission
was Fortran 77 and K&R C for some computers we then made, so I've been
poked with both ends of this stick.  

 
> > Because of the need to talk to entities written in languages other than
> > Ada95, or in Ada95 but compiled and linked at a different time perhaps
> > using a different compiler and compiler version, the specific enumeration
> > mapping must be explicitly nailed down, with no discretion left to any of
> > the various compilers.  This was the reason for the rep specs.  Now that
> > the rep specs are gone, some other equivalent method will be needed.  
> 
> Huh? What do you mean?  Last time I checked, rep specs were very much
> alive and well in Ada95!  Or do you simply mean that your project has
> chosen to give up on using rep specs for some incomprehensible reason
> ... ? :-)

Whoa!  What we have given up on are rep specs on enumeration types, not
rep specs in general.   

And, we find a 100:1 to 1000:1 performance hit to be simply intolerable,
not just incomprehensible.  It's all too comprehensible; projects have
died for less. 

Joe Gwinn