Re: Future Direction of GNU Hurd?
"Jonathan S. Shapiro" <[email protected]> Tue, 16 Mar 2021 11:39:39 -0700
| Newsgroups | gmane.os.hurd.l4 |
|---|---|
| Message-ID | <CAAP=3QN1HbRbSH_H=+EFpOmTG+8KGNyOYFCToJo6+UKREmDtxw@mail.gmail.com> |
--00000000000003ec6d05bdabb1e9 Content-Type: text/plain; charset="UTF-8" On Sun, Mar 14, 2021 at 11:23 AM Olaf Buddenhagen <[email protected]> wrote: > > One of the critical notions in capabilities is > > that the capability you wield names the object you manipulate. If the > > receive port can be transferred, this intuition is violated. In > > consequence, few capability-bases systems have implemented receive > > ports. > > Interesting... Didn't realise that this is something capability designs > frown upon. > I just realized that I need to clarify this, because I wasn't using "object" in the way that I think it is being understood. When I say that a capability names a specific object, two things are true: 1. The term "object", in this context, means "state + behavior", not necessarily the specifically executing implementation. 2. When objects are "active" (that is: implemented by services), it is possible for the API or interface of the object to change dynamically. From an application perspective, it may be useful to think of the result as a new object, but for the purposes of understanding capabilities it isn't. The capacity to "morph" its operation set was part of the specification of the original behavior of the object. Because of this, the *new* behavior of the object is conceptually included in the original behavior. In the current discussion, this comes up as follows: The Coyotos "Endpoint" object contains a *process* capability to the receiving process (note: *not* an entry capability!). It's a scheduler activation design, so the effect of message arrival is (a) mark in the shared page that a message is waiting and (b) if the process is sleeping, wake it up so that it notices. The tricky part in scheduler activations on a multiprocessor is that these two things can be in a race. Anyway, the receiving process typically holds the "master" capability to the endpoint, *so it is in a position to change the process capability*. If it does so, the recipient process changes. This is very similar to the notion of a receive port or receive capability. The reason this is OK is that the *original* recipient process could equally well implement this by forwarding the message to the *new* recipient process. That is: changing the process capability in the endpoint is logically equivalent to forwarding the message. Note that this would not be possible in the Mach reply capability design, because that capability cannot be forwarded. It requires an explicit reply capability that can be forwarded. Ironically, the inability to forward the *reply* capability means that forwarding the *receive* capability needs some care. If I remember correctly (hey, it's only been 38 years), Mach is even weirder, because a reply port is part of the *process* state rather than the *thread* state. A message received by one thread can be replied by a different thread in the same process, but cannot be replied by a different process. This creates a strange asymmetry. FWIW, I was personally never able to conclude whether the ability to > transfer receivers is a useful feature in general or not. > The ability to transfer the authority to *reply* is fairly essential. This was a pretty fundamental design mistake in Mach IPC. The ability to transfer receive ports/capabilities is less so, but there is no semantic or security problem with it - it's equivalent to receiving and forwarding all messages to the new receiver. > > No member of the KeyKOS family implemented such a notion. Coyotos > > comes closest. "Entry" capabilities actually point to Endpoint > > objects, which in turn contain a Process capability to the > > implementing process. A scheduler activation is performed within this > > process. This is comparable to a receive port capability because the > > process capability within the Endpoint object can be updated. > > Will have to think about whether such a design would work for what I'm > trying to do. > Given my explanation above, I think it will, because you can implement something equivalent to transferring the receive port. > I totally agree that it's probably not useful to have multiple active > listeners... It's not what I'm looking for :-) > It isn't obvious. The problem in a multiprocessor is that two different receive threads on the same endpoint may have message receive times that are different by several orders of magnitude. There is no place outside the kernel where choosing the receiver can be done well. > This also has the advantage that all of the "pointers" (the object > > references) point from the invoker to the invokee. That turns out to > > be essential if you want to implement transparent orthogonal > > persistence. It rules out receive port capabilities. > > That's funny: the thing that (I think) I need receiver capabilities for, > is actually for implementing a (not quite orthogonal) persistence > mechanism :-) > Feel free to steal what we did. The EROS version is pretty thoroughly written up. The Coyotos version was never implemented, but the way we modified the "range" architecture, the migration to a more conventional, multi-generational write ahead log for checkpoint, and the fact that no object has multiple "interpretations", makes it a whole lot simpler. The hardest part of persistence in EROS was that the "node" object had so many possible interpretations that needed to be taken into account. The WAL implementation *was* completed in later versions of EROS, so it should be possible to borrow that. One the problem with orthogonal persistence is that it doesn't actually simplify much in networked systems. Two processes running on the same machine will be restored in a mutually consistent way, but processes running on *different* machines will not. This tends to mean that communications across the machine perimeter behave very differently, and a lot of processes need to know about it. The truth is that these two cases have *always* behaved differently, but UNIX and Windows go to extreme lengths to hide this from applications (unsuccessfully, because it can't be done in principle when messages cross failure domains). The other problem is that you sometimes *need* to violate orthogonality. For example, you don't want to lose a committed banking transaction if the system has to restart before the next checkpoint. KeyKOS, EROS, and Coyotos *all* have ways to bypass the checkpoint rules for this kind of situation. In abstract, we know how to build a multi-machine cluster that acts *as if* it were a single failure domain - I wrote a paper about it decades ago, but never published it because it was never implemented. The hard part is bounded rollback using local checkpoint. If anybody cares I can say more about it. But even if you do this, there will still be "foreign" systems you need to talk to. The problem of independent failure domains isn't going to go away, and once you have to deal with it *anywhere* the incentive to expand individual failure domains is greatly reduced. > > I have not looked at Viengoos, but this sounds functionally similar to > > what Coyotos does. In Coyotos, the receiving process designates a > > scheduler activation block that says where the incoming data should > > go. > > Although I don't know the full history, > the Viengoos approach is quite likely inspired by the Coyotos one... I didn't know anything about Viengoos until Neal arrived at Johns Hopkins. I don't know what may have happened afterwards, but in my interactions with Neal the Viengoos design seemed pretty well decided. So far as I know, Coyotos did not borrow from Viengoos. Coyotos was leveraging almost 35 years of concrete experience with a particular type of system architecture, and attempting to merge what we had learned in our verification efforts. Initially, it started because I wanted to look at how the "unit of operation" intuition (which was SO critical) would work in a multiprocessor variant. Viengoos, at that time, was a young design, and Neal was still exploring. Jonathan --00000000000003ec6d05bdabb1e9 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable <div dir=3D"ltr"><div dir=3D"ltr">On Sun, Mar 14, 2021 at 11:23 AM Olaf Bud= denhagen <<a href=3D"mailto:[email protected]">olafbuddenhagen@gmx= .net</a>> wrote:<br></div><div class=3D"gmail_quote"><blockquote class= =3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rg= b(204,204,204);padding-left:1ex">> One of the critical notions in capabi= lities is<br> > that the capability you wield names the object you manipulate. If the<= br> > receive port can be transferred, this intuition is violated. In<br> > consequence, few capability-bases systems have implemented receive<br> > ports.<br> <br> Interesting... Didn't realise that this is something capability designs= <br> frown upon.<br></blockquote><div><br></div><div>I just realized that I need= to clarify this, because I wasn't using "object" in the way = that I think it is being understood. When I say that a capability names a s= pecific object, two things are true:</div><div><div><ol><li>The term "= object", in this context, means "state=C2=A0+ behavior", not= necessarily the specifically executing implementation.</li><li>When object= s are "active" (that is: implemented by services), it is possible= for the API or interface of the object to change dynamically. From an appl= ication perspective, it may be useful to think of the result as a new objec= t, but for the purposes of understanding capabilities it isn't. The cap= acity to "morph" its operation set was part of the specification = of the original behavior of the object. Because of this, the <i>new</i>=C2= =A0behavior of the object is conceptually included in the original behavior= .=C2=A0</li></ol></div></div></div>In the current discussion, this comes up= as follows:<div><div><br></div><div>The Coyotos "Endpoint" objec= t contains a <i>process</i>=C2=A0capability to the receiving process (note:= <i>not</i>=C2=A0an entry capability!). It's a scheduler activation des= ign, so the effect of message arrival is (a) mark in the shared page that a= message is waiting and (b) if the process is sleeping, wake it up so that = it notices. The tricky part in scheduler activations on a multiprocessor is= that these two things can be in a race. Anyway, the receiving process typi= cally holds the "master" capability to the endpoint, <u>so it is = in a position to change the process capability</u>. If it does so, the reci= pient process changes. This is very similar to the notion of a receive port= or receive capability.</div><div><div><br></div><div>The reason this is OK= is that the <i>original</i>=C2=A0recipient process could equally well impl= ement this by forwarding the message to the <i>new</i>=C2=A0recipient proce= ss. That is: changing the process capability in the endpoint is logically e= quivalent to forwarding the message.</div><div><br></div><div>Note that thi= s would not be possible in the Mach reply capability design,=C2=A0because t= hat capability cannot be forwarded. It requires an explicit reply capabilit= y that can be forwarded. Ironically, the inability to forward the <i>reply<= /i>=C2=A0capability means that forwarding the <i>receive</i>=C2=A0capabilit= y needs some care.</div><div><br></div><div>If I remember correctly (hey, i= t's only been 38 years), Mach is even weirder, because a reply port is = part of the <i>process</i>=C2=A0state rather than the <i>thread</i>=C2=A0st= ate. A message received by one thread can be replied by a different thread = in the same process, but cannot be replied by a different process. This cre= ates a strange asymmetry.</div><div><br></div><div><div class=3D"gmail_quot= e"><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;bord= er-left:1px solid rgb(204,204,204);padding-left:1ex">FWIW, I was personally= never able to conclude whether the ability to<br> transfer receivers is a useful feature in general or not.<br></blockquote><= div><br></div><div>The ability to transfer the authority to <u>reply</u> is= fairly essential. This was a pretty fundamental design mistake in Mach IPC= . The ability to transfer receive ports/capabilities is less so, but there = is no semantic or security problem with it - it's equivalent to receivi= ng and forwarding all messages to the new receiver.</div><div>=C2=A0</div><= blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-l= eft:1px solid rgb(204,204,204);padding-left:1ex">> No member of the KeyK= OS family implemented such a notion. Coyotos<br> > comes closest. "Entry" capabilities actually point to Endpoi= nt<br> > objects, which in turn contain a Process capability to the<br> > implementing process. A scheduler activation is performed within this<= br> > process. This is comparable to a receive port capability because the<b= r> > process capability within the Endpoint object can be updated.<br> <br> Will have to think about whether such a design would work for what I'm<= br> trying to do.<br></blockquote><div><br></div><div>Given my explanation abov= e, I think it will, because you can implement something equivalent to trans= ferring the receive port.</div><div>=C2=A0</div><blockquote class=3D"gmail_= quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,= 204);padding-left:1ex">I totally agree that it's probably not useful to= have multiple active<br> listeners... It's not what I'm looking for :-)<br></blockquote><div= ><br></div><div>It isn't obvious. The problem in a multiprocessor is th= at two different receive threads on the same endpoint may have message rece= ive times that are different by several orders of magnitude. There is no pl= ace outside the kernel where choosing the receiver can be done well.</div><= div><br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px= 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">> This a= lso has the advantage that all of the "pointers" (the object<br> > references) point from the invoker to the invokee. That turns out to<b= r> > be essential if you want to implement transparent orthogonal<br> > persistence. It rules out receive port capabilities.<br> <br> That's funny: the thing that (I think) I need receiver capabilities for= ,<br> is actually for implementing a (not quite orthogonal) persistence<br> mechanism :-)<br></blockquote><div><br></div><div>Feel free to steal what w= e did. The EROS version is pretty thoroughly written up. The Coyotos versio= n was never implemented, but the way we modified the "range" arch= itecture, the migration to a more conventional, multi-generational write ah= ead log for checkpoint, and the fact that no object has multiple "inte= rpretations", makes it a whole lot simpler. The hardest part of persis= tence in EROS was that the "node" object had so many possible int= erpretations that needed to be taken into account. The WAL implementation <= i>was</i>=C2=A0completed in later versions of EROS, so it should be possibl= e to borrow that.</div><div><br></div><div>One the problem with orthogonal = persistence is that it doesn't actually simplify much in networked syst= ems. Two processes running on the same machine will be restored in a mutual= ly consistent way, but processes running on <i>different</i>=C2=A0machines = will not. This tends to mean that communications across the machine perimet= er behave very differently, and a lot of processes need to know about it. T= he truth is that these two cases have <i>always</i>=C2=A0behaved differentl= y, but UNIX and Windows go to extreme lengths to hide this from application= s (unsuccessfully, because it can't be done in principle when messages = cross failure domains).</div><div><br></div><div>The other problem is that = you sometimes <i>need</i>=C2=A0to violate orthogonality. For example, you d= on't want to lose a committed banking transaction if the system has to = restart before the next checkpoint. KeyKOS, EROS, and Coyotos <i>all</i>=C2= =A0have ways to bypass the checkpoint rules for this kind of situation.</di= v><div><br></div><div>In abstract, we know how to build a multi-machine clu= ster that acts <i>as if</i>=C2=A0it were a single failure domain - I wrote = a paper about it decades ago, but never published it because it was never i= mplemented. The hard part is bounded rollback using local checkpoint. If an= ybody cares I can say more about it.=C2=A0 But even if you do this, there w= ill still be "foreign" systems you need to talk to. The problem o= f independent failure domains isn't going to go away, and once you have= to deal with it <i>anywhere</i>=C2=A0the incentive to expand individual fa= ilure domains is greatly reduced.</div><div><br></div><div>=C2=A0<br></div>= <blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-= left:1px solid rgb(204,204,204);padding-left:1ex">> I have not looked at= Viengoos, but this sounds functionally similar to<br> > what Coyotos does. In Coyotos, the receiving process designates a<br> > scheduler activation block that says where the incoming data should<br= > > go.<br> <br>Although I don't know the full history,<br> the Viengoos approach is quite likely inspired by the Coyotos one...</block= quote><div><br></div><div>I didn't know anything about Viengoos until N= eal arrived at Johns Hopkins. I don't know what may have happened after= wards, but in my interactions with Neal the Viengoos design seemed pretty w= ell decided. So far as I know,=C2=A0Coyotos=C2=A0did not borrow from Viengo= os. Coyotos=C2=A0was leveraging almost 35 years of concrete experience with= a particular type of system architecture, and attempting to merge what we = had learned in our verification efforts. Initially, it started because I wa= nted to look at how the "unit of operation" intuition (which was = SO critical) would work in a multiprocessor variant. Viengoos, at that time= , was a young design, and Neal was still exploring.</div><div><br></div><di= v><br></div><div>Jonathan</div></div></div></div></div></div> --00000000000003ec6d05bdabb1e9--