Re: On hierarchy

[Udo A. Steinberg]

On Fri, 21 Oct 2005 16:26:06 -0400 Jonathan S. Shapiro (JSS) wrote:

JSS> On Fri, 2005-10-21 at 20:22 +0200, Udo A. Steinberg wrote:
JSS> > 
JSS> > In order to use compatible terminology, please write "preemptible" ;)
JSS> 
JSS> Happily. My splling is terribull. Actually, I believe that the correct
JSS> spelling in this case is with an "a".

The following web page attempts to shed some light on the issue
http://www.linuxdevices.com/articles/AT5136316996.html

and the arguments by Bill Weinberg make sense to me. But I'm by no means an
English linguist, so maybe you can provide some insight why you think it
should be "preemptable".

JSS> Yes. I was aware of this. There are two cases in the API that I do not
JSS> understand how to implement correctly if operations are preemptable. Can
JSS> you explain them:
JSS> 
JSS> 1. Two threads exist in a task. One performs an unmap from a location
JSS> while the other (simultaneously) executes a loop performing a map. Is
JSS> the unmap guaranteed to terminate in any predictable amount of time?

The thread invoking unmap will lock down the affected (sub)tree of the page
frame in question and the thread invoking map can no longer add new nodes
in that subtree. It can, however, add new nodes upstream, i.e., in a
different subtree (from the root node's POV).

JSS> 2. One thread performs a long unmap that is preempted after making
JSS> partial progress. Because it is preempted, the scheduler permits other
JSS> threads to run. In particular, a debugger thread performs a "stop"
JSS> operation on the thread that is performing the UNMAP. I do not see any
JSS> outcome in which this is possible within the requirements I have stated
JSS> without leaving the system overall in an inconsistent state.

The thread with a preempted unmap is inside the kernel at the time of the
"stop" operation. It can run the unmap to completion but it must not return
to user mode in order to maintain the "stop" semantics for the user.

JSS> Unfortunately, none of these mechanisms work in the general case -- a
JSS> discussion we should take up separately. The problem is that there is no
JSS> way in general to know which thread to escalate if the IPC mechanism is
JSS> general-purpose. Both the L4 and EROS IPC mechanisms are general
JSS> purpose.

I don't understand your concern here. Both with locks and with IPC you can
have one thread depend on another. Both issues can employ some sort of
helping or time/priority donation to prevent priority inversion.

JSS> Setting this aside, long-held locks also create opportunities for kernel
JSS> deadlock that we would prefer to avoid, and they make analysis of kernel
JSS> correctness about two orders of magnitude harder. I don't know if formal
JSS> analysis is an active objective for L4.sec, but for Coyotos this is
JSS> definitely a concern.

Short-held locks will deadlock the same way long-held ones do, if you don't
preclude deadlocks by careful system design.

JSS> If I understand you, this is the case where the unmap is a total unmap:
JSS> the PTE's are going to invalid. I had in mind a different algorithm, but
JSS> I agree that yours works. Also, I *think* that your solution resolves my
JSS> "map during unmap" question.
JSS> 
JSS> The case that I do not currently understand how to do is the *partial*
JSS> unmap -- e.g. taking away write permission while leaving read
JSS> permission. For this case, I think you will need to add some form of
JSS> index to keep track of progress. Is there a way around this?

It's late and I fail to see how downgrading rights from read/write to
read-only is any different from downgrading rights from present to
non-present, except that we don't deallocate the affected nodes.
Can you provide an example that illustrates your point?

JSS> Do the performance measurements that have been published for the map
JSS> operation include this locking, or are they measuring an incorrect
JSS> implementation?

Which performance numbers are you referring to?

-Udo.

pgpOyx2bJJICK.pgp
Description: PGP signature