From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,ca9eef4d5e2078ea X-Google-Attributes: gid103376,public From: gwinn@res.ray.com (Joe Gwinn) Subject: Re: Beware: Rep spec on an enumeration type causes code explosion Date: 1997/12/18 Message-ID: X-Deja-AN: 299371493 Content-Transfer-Encoding: 7bit References: <348F3DFC.10DB@nospam.flash.net> <3490252D.6B550F17@ac3i.dseg.ti.com> <3496D55F.1312429E@ac3i.dseg.ti.com> <34989D6B.402AE2A7@ac3i.dseg.ti.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Organization: Raytheon Electronic Systems Newsgroups: comp.lang.ada Date: 1997-12-18T00:00:00+00:00 List-Id: 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