[coyotos-dev] IDL compatibility

Jonathan S. Shapiro shap at eros-os.com
Tue Jun 19 12:22:27 EDT 2007

On Tue, 2007-06-19 at 08:36 -0700, Charles Landau wrote:
> At 10:46 AM -0400 6/19/07, Jonathan S. Shapiro wrote:
> >This is not inconsistent. It is *required*. These method declarations
> >appear in distinct packages. They are distinct exceptions and must be
> >assigned distinct codes.
> No, only values in a single chain of inheritance must be distinct. 
> This example has completely distinct chains.

Yes. I made the same point later in my note. This is why a 32-bit
cryptographic code point assignment for method names is acceptable.

> >Cryptographic code points are regrettable because they cannot be
> >efficiently demultiplexed. The problem with any *other* method code
> >synthesis scheme is that central coordination is required to avoid code
> >point collisions.
> There are many schemes that could avoid collisions in a single chain 
> of inheritance. You could have an easily-demultiplexed method index 
> in the low bits, and (only for robustness, in case a method code is 
> misused) a hash in the high bits.

The current scheme is that the most-significant 8 bits encode the
inheritance depth, with the "root" value being 1 (to guarantee
non-collision with RC_OK). The least-significant 24 bits are the method
number in order of appearance within the interface.

This is not a good scheme. It is vulnerable to many innocuous edits that
can cause method codes to be inadvertently altered. Unfortunately, I do
not know of any implicit code point assignment strategy *other* than a
pure hash on fully-qualified name (or reliably random generation) that
does not share this issue.

Using inheritance depth was also a mistake. We have already seen cases
where method names have needed to migrate and/or interfaces have needed
to be injected into a hierarchy.

CapIDL will support hand-assignment of method codes at some point; MarkM
and I recognized the need for this (due to compatibility issues) from
the beginning. The goal is to minimize hand assignment and to *strongly*
discourage any code point model that would lend itself to collisions
when methods need to be relocated and/or rearranged.

Realistically, the only mechanisms I know about that satisfy all of
these objectives are strongly random assignment and cryptographic
hash-based assignment. The latter has the advantage of determinism, and
eliminates the need to hand-assign code points to every method during
development (which lowers cost of adoption of CapIDL, which is good).

> >The current exception code scheme will fail if more
> >than 2^16 exceptions come to exist system-wide, and I am of the opinion
> >that exception code values should be increased to 64 bits to avoid this.
> That would reduce the probability of collision, but not to zero, and 
> at a runtime cost.

There is, in principle, no way to reduce the probability of collision to
zero. The collision probability from cryptographic hashes is orders of
magnitude lower than any known human-assigned scheme -- including the
one you proposed below (discussion follows below).

The runtime cost is largely irrelevant. These are low-frequency results,
and in practice it is rare for the receiver to attempt to recover from
more than one or two exception types. Unless the receiver actually
handles a large number of exception cases explicitly, the marginal
runtime cost of a 64-bit exception code is essentially zero.

> The way to absolutely guarantee non-collision is to declare all the 
> exceptions at one level. Unix's errno.h demostrates that that's 
> feasible. cap.idl already declares exceptions that are only used by 
> derived interfaces.

Please explain how I can declare all exception codes that will be needed
by developers who are designing an unanticipatable application 25 years
from now.

The current mechanism effectively accomplishes what you suggest, but it
is much more future-proof.

errno.h is a wonderful illustration of how to do it wrong. As errors
were added to errno.h by different vendors, there were collisions.
Cleaning up errno code point discrepancies is one of the real annoyances
that has to be dealt with when implementing binary support for different
unix personalities in a single system.

The entire problem with errno.h is that the code points were selected in
a political namespace (i.e. one run by humans) rather than a randomized
one. Had they been randomly assigned, no reconciliation would have been
needed at all.

> People are still free to declare their own exceptions locally, they 
> just can't propagate them with any guarantee of uniqueness.

As errno.h has demonstrated over the years, this is equally true for
centrally assigned error number code points.


More information about the coyotos-dev mailing list