Re: A comment about changing kernels

[Jonathan S. Shapiro]

On Wed, 2005-11-02 at 13:36 +0100, Espen Skoglund wrote:
> > The correct behavior was to save the segment selectors, and this
> > adds about 20 cycles to the path. This means that the reported small
> > space performance figure of 135 cycles/IPC was actually low by about
> > 15% relative to a correct implementation. So the situation was that
> > the (incorrect) L4 path was compared to the (correct) EROS path to
> > suggest equal performance, but a corrected L4 path would have been
> > measurably slower.
> 
> As you say yourself, this has nothing to do with the IPC path.  And as
> Bernhard pointed out, this is purely an interrupt handling issue.
> 
> I've also said that implementing small spaces without reloading
> segment registers on IPC is *not* possible.  Your statement above is
> therefore a blatant lie.

Espen:

In fact, it is only a misunderstanding that has taken a while to
sort out. The *critical* clarifying statement arrived only in your very
latest email -- or at least, this is the first time that I have
understood it. Knowing you, I assume that your words are the result
of extreme frustration rather than considered intent.

All: I have had a chance to think through Espen's latest comments, and
he is correct. There is no bug in the L4 IPC path, except possibly a
documentation bug. I have been traveling, so I have not been able to
check, but I do not *remember* the IPC specification documenting that
segment selectors are restored to known values by the IPC operation. The
rationale that justifies the current behavior is, in my opinion,
obscure, but it is correct. Let me try to walk everyone through the
discussion in order to confirm what has converged.

1. We seem to have confirmed that there *is* a significant security
exposure in that implementation's interrupt handling path. I need to
check, but my memory is that the register save portion of the interrupt
entry path and the IPC entry path were common code. If so, the selector
values are not being saved when an interrupt causes a process to enter
the kernel in that particular L4 implementation. This needs to be
checked.

Why would this be a hazard?

It allows an arbitrary, non-privileged process to make fairly accurate
measurements of interrupt frequency and timing. The level of information
obtained is almost certainly good enough for a process with a high
dynamic priority to exploit the old SSH password keystroke timing
analysis vulnerability, or similar vulnerabilities in interrupt timing
analysis that may arise in the future.

This has absolutely nothing to do with whether the segment base and
limit are reloaded by a full context switch from process A to process B.
The base and limit reload is a question of a state change between the
incoming state of process A and the outgoing state of process B. The
issue in the selector reload is that when process A takes an interrupt,
and is later rescheduled, its **selector** values may not match the ones
that existed at the time of the interrupt. That is, I am talking about
the restoration of process state after a *sequence* of context switches
of
the form

        A -> ... -> A

Bernhard's comments about small space switch are completely correct, but
not relevant to this discussion. It is definitely NOT correct that small
spaces require any observable change in the restore of selector values
during IPC. The selector also does not need to change when the small
space size is adjusted -- this can be avoided by overwriting the GDT in
place. The segment *limit* must change when the small space size is
adjusted, but this does not generally occur as the result of an
interrupt or (in most cases) an IPC.

2. The L4 IPC implementation was correct. *My* mistake was in being
misled by my own expectations. I assumed that any register that is *not*
used in some fashion by the IPC trap should be restored unmolested when
the *sending* process later resumes execution. The idea that a system
call should mangle innocent and uninvolved registers, and the
consequence that any process wishing to *preserve* its segment registers
across IPC must take special action seems counter-intuitive and
obfuscated to me (that is an aesthetic judgment, not a technical
judgment).

However, if the overwhelming majority of processes do not alter their
segment selectors (which is true), then it is a valid technical choice
to place the burden only on those processes that do. If this is done,
then several very unpleasant side effects of a bad processor
specification can be avoided in the IPC path (but not in the interrupt
return path, which *must* preserve selector values).

Espen implies that this decision was intentional. If so, it is puzzling
that Jochen did not point this out when I described this issue to him in
2000. On the contrary, Jochen *agreed* that this was a bug. Because he
agreed, I did not investigate the matter further. 

>   Additionally, if you look at Jochen's
> numbers (the 135 cycles number you refer to) the slides he used for
> presenting these numbers explicitly state that so and so many cycles
> were spent reloading segment registers.

The segment registers were absolutely reloaded. However, they were not
saved. That is: they were reloaded, but not restored. It is the cost of
the *save* that is missing in the numbers, but as I have stated above,
this save is not actually required in the IPC path.

With the corrected understanding, my statement about the performance of
the two systems certainly needs to be revised. The L4 IPC number quoted
at ~135 cycles is based on a correct implementation. The EROS number was
approximately the same speed, but could have been improved by about 5%
to 10% by exploiting the same optimization.

> I'm only pointing this out because you have a tendency of
> presenting your own interpretations and beliefs as "truth".  Sure, in
> some cases you may simply be inaccurate, ill informed, or not remember
> exactly what has previously been said, but in these cases you should
> have the decency to clearly express so.

Espen: it is our *jobs* as engineers to state the results of our
analysis and their implications, even when it later proves that these
are wrong. It is also our jobs to correct our mistakes after we come to
understand them. To my knowledge, I have *never* failed to acknowledge
such an error once it has become clear to me. Can you name a *single*
instance in which this has not been true? Conversely, can you identify a
single case in which any member of the L4 community has retracted
erroneous statements about *my* work? None of us are perfect.

In this particular case, my conduct was proper in all respects. After
identifying the bug, I brought it to the attention of the architect and
implementor, who *agreed* that it was a bug. You will perhaps forgive me
for granting Jochen the courtesy of believing him about his own code?
And for checking with him before publishing? And even, I hope, for
accepting his statement ahead of your opinion and Bernhardt's while the
discussion remained confused?

Bernhardt's comments did, in hindsight, deserve closer attention. The
non-relevance of his comments (and yours) about segment reload did not
suggest to me that he (or you) understood correctly the issue that I was
actually raising. This was compounded by a logic error: he made a
statement of the form "X is necessary for Y, therefore X is correct".
This is simply bad reasoning, since it is equally possible in an
argument of this form that X is wrong and therefore Y is *incorrect*.

Espen, between funding my students, preparing and teaching courses,
discharging my administrative responsibilities, overseeing my students,
supporting my clients, and other activities, I regret that I do not have
time to debug every email that I receive. In my copious spare time over
the past three weeks, I have been either traveling non-stop or spending
time in the emergency room with my infant son, or remaining awake most
of the night with my wife to hold him upright because he could not
breath reliably while lying down. I have not slept much during that
time. You, of course, would do better, but *I* am only human.

I will assemble a web page on the EROS site clarifying the current
discussion and the get Geoff Voelker to send out a note to the SIGOPS
list about it. Not because you complained, but because it is the only
possible professionally responsible action. If you can see a better way
to reach the relevant audience, please do not hesitate to let me know.


shap