l4-hackers December 2003

l4-hackers@os.inf.tu-dresden.de

17 participants
20 discussions

RE: IPC/Capabilities Overview
by Volkmar Uhlig 04 Jan '04

04 Jan '04

> -----Original Message----- > From: Jonathan S. Shapiro [mailto:shap@eros-os.org] > Sent: Wednesday, December 31, 2003 6:32 AM > > First, some corrections on specific statements that you made, because > they are potentially distracting from the real issues. Then I will try > to answer your questions. > > Corrections: > > 1. L4 IPC speed has relatively little to do with the "direct lookup" > aspect of thread ids. Any indirect encoding will carry a cost, … [View More]but in > terms of the overall performance of IPC this cost is quite small. That is wrong. The direct lookup drastically reduces cache and TLB footprint. For a full IPC we have to access two TCBs (which are virtually mapped and have the stack in the same page) which costs two TLB entries. The complete lookup is therefore a simple mask (plus maybe a shift), a relative mov (e.g. mov 0xe0000000(%eax), %ebx) and a compare. Overall costs therefore (on IA32): - 2 TLB entries (but we need them anyway for the stack, they could be reduced to one TLB entry when using 4M pages for all TCBs, but that would add an indirection table and therefore a cache line); refetch costs ~80 cycles/entry - shift and move (~3 cycles) - 1 cache line for the thread id (which is shared with thread state etc). Assume you add 2 more TLB entries and 5 more L2 cache lines--your aftercosts for IPC go up by 2*80 + 5*80 = 560 cycles. Considering overall IPC costs of 1000 cycles on a P4 with all those nasty cache and TLB flushes you add an overhead of >50%. > 2. Security checks done in the server vs. the kernel are not > necessarily slower or faster. It depends greatly on what security > checks you wish to do. I argue that: > > a) *many* (not all) of the security checks currently done in L4 > servers could be eliminated if kernel-protected bits existed > in each descriptor > > b) For some types of systems (capability systems), disclosure of > the sender id is an absolute violation of design requirements, > so any microkernel that relies exclusively on server-side > security checks based on sender-id is not a universal > microkernel. > > c) More specifically, any microkernel that requires checks based > on sender-id is entirely unsuitable as a platform for EROS-NG. And as you stated this is _also_ a limited view, because you only look from the EROS and capability point of view. By throwing away one register for an identifier you reduce your register real estate by 33%. That can be particularly hurtful in the local case, where a very simple check (or none) is sufficient. And the argument that everything should go in memory (one of your last emails) is not convincing--register-based IPC is still much faster, it is mostly a question of a reasonable IDL compiler. And we are all aware that IA32 is crippled from that perspective. Take any other architecture (worst case: IA64) and the argument becomes complete bogus. > Ignoring clans and chiefs (which we all agree is too expensive and > inflexible), here is how the three schemes break down: > > Thread IDs: > No restriction who can send. > Server makes decisions based on sender-id You forgot sender restriction and redirection. > Hybrid: > Sender can only invoke a thread descriptor that is mapped in their > thread descriptor space (thread space) > Server makes decisions based on either (a) a field that is encoded > within the descriptor, or (b) the sender-id. > > ** Sender-id is software controlled by the thread manager, and can > be set to zero for all threads to simulate capability behavior. A possibility you did not mention is a hybrid thread id which has an thread and a descriptor part. The descriptor is kernel enforced. That is what we currently have in V4 (please not that V2 and X.0 are completely outdated!!!)--the version part of the thread id. > In the thread-IDs design, there are two distinguished phases in the > server-side security checks: > > 1. Object resolution. Based on sender-id and arguments, determines > the identity and permissions of the server-implemented object > that has been invoked. This phase may conclude that no such > object exists. > > 2. Permissions check. Given the object identity and permissions, > make a decision about whether the particular operation is to be > permitted. > > All of the bits needed for phase 2 can be encoded in the > descriptor. All of the expensive parts of the current L4 protocol > lie in phase 1 (object resolution). See above. Furthermore, your suggestion is to move that part into the kernel... Then the overhead is on _every_ invocation, not just for the once where you need it. > > Now I want to make clear why capablities are much better > than virtual thread > > objects: > > > > * The extra word does not seem to decrease performance in > any way (is this > > true?) so it a free feature, that can be used but doesn't have to. > > I believe that this is true, and the evidence of the EROS > implementation seems to support this view. Where are benchmarks with cold caches? Do you have a detailed analysis of the cache and TLB footprint? > This is a possible usage. In our experience, the more common > behavior is > to have a pointer to some data structure that describes a server > implemented object (i.e. has nothing to do with any > particular client), > and reuse the low bits for permissions. For example, the pointer might > point to a file metadata structure, and the low bits might > indicate read and write permissions. In our case we use an object identifier in the message, which is a handle to an object descriptor and do a reverse check (i.e. if the thread is allowed to invoke that object). Costs: boundary check (can be a simple AND) one MOV and a CMP. The permissions can go into the same cache line. Happy new year!!! - Volkmar [View Less]

4 3

Re: IPC/Capabilities Overview
by Rudy Koot 01 Jan '04

01 Jan '04

>Corrections: > >1. L4 IPC speed has relatively little to do with the "direct lookup" >aspect of thread ids. Any indirect encoding will carry a cost, but in >terms of the overall performance of IPC this cost is quite small. While this is indeed also my believe, it unfortunately isn't that of the L4 team. If you look at their presentation their two main points are: "IPC needs to be infinitly fast". The problem is that they only look at direct costs of cycles spend on entering … [View More]the kernel, doing IPC and exiting tthe kernel. They also look at indirect costs of TLB and cache misses caused by IPC, but strangely enough won't look at the cost of checking access rights (probalby because access checks are no longer part of the microkernel, but of operating system policy). If you want to convince them, you have to make sure they eiter count those costs also OR make sure they believe the added IPC costs of capabilities are indeed neglectable. As far as I could reason these added (compared to the thread-id methode) costs would be: - One extra register spilled on the receiver side (to store the server defined word) - One extra memory access (to convert the capability into the server thread id) [VTO] - One extra memory access (to load the server defined word) - One or more extra memory accesses (to locate the server defined word and server thread id in the Thread Object Space) [VTO] This goes in against their believe that "A computers get faster memory acess get relativly slower, therefore memory access should be avoided during IPC". I believe only 2 memory accesses are needed on RISC machines with large register sets, so the 3+ extra accesses are quit a burden (through the L4 developer's eyes). However they are considering Virtual Thread Objects and compared to that only 1 extra memory access is required (this isn't a lost comparing against the 4+ that already need to be done), because the steps marked with [VTO] needs to bee done in that model also. > b) For some types of systems (capability systems), disclosure of > the sender id is an absolute violation of design requirements, > so any microkernel that relies exclusively on server-side > security checks based on sender-id is not a universal microkernel. I never realised this, and I still don't see why this a design requirement, but if there is one this would again be a major argument in favor of capabilities. Could you give me an example of when not reveiling sender-id is useful? >Hybrid: > Sender can only invoke a thread descriptor that is mapped in their > thread descriptor space (thread space) > Server makes decisions based on either (a) a field that is encoded > within the descriptor, or (b) the sender-id. > > ** Sender-id is software controlled by the thread manager, and can > be set to zero for all threads to simulate capability behavior. Could you explain a bit more about this thread manager. It seems to solve a problem in which the sender id does needs to be know. For example if a thread tries to write to a file, which it hasn't got write access for, it may be a system requirement that this is logged into the security log. Now you also want to log which thread actualy made the violation. If the sender-id isn't reveiled to the file server it can only log the thread-id (no not thread-id, something else but what?) to which it originally mapped the capability. Maybe if a thread manager is used the true sender-id can be logged withour reveiling it so the file server itself? > > * The server defined word will probably be used to store a pointer to >some > > client specific data structure containing important information that >needs > > to be access often. You might say, yeah well mbut you can calculate this > > address from the sender ID, but this no longer works when clients start >to > > grant and map server objects/capabilites to eachother, because the >server > > doesn't know about these actions, unless some complex, slow protocol is >used > > to update the serves information. > >This is a possible usage. In our experience, the more common behavior is >to have a pointer to some data structure that describes a server >implemented object (i.e. has nothing to do with any particular client), >and reuse the low bits for permissions. For example, the pointer might >point to a file metadata structure, and the low bits might indicate read >and write permissions. I used some strange wording in my explanation but a meant what you just said. > > The size of the > > capability should be equal to the pointer/word size of the machine. > >This can't be true, since the capability must encode both the >destination thread id and also the extra word. Minimum practical size is >two machine words. Sorry this was a typo, I Actually meant to say the size of the server defined word inside the capability shouls be aqeual to the machine word size, making the total capability size, indeed, at least 2 machine words in size. -- Rudy Koot _________________________________________________________________ MSN Zoeken helpt je om de gekste dingen te vinden! http://search.msn.nl [View Less]

3 3

RE: IPC/Capabilities Overview
by Volkmar Uhlig 01 Jan '04

01 Jan '04

> -----Original Message----- > From: Rudy Koot [mailto:rudykoot@hotmail.com] > Sent: Wednesday, December 31, 2003 11:39 AM > The problem is that they only look at direct > costs of cycles spend on entering the kernel, doing IPC and > exiting tthe kernel. They also look at indirect costs of > TLB and cache misses caused by IPC, but strangely enough won't > look at the cost of checking access rights (probalby because > access checks are no longer part of the … [View More]

2 1

IPC/Capabilities Overview
by Rudy Koot 31 Dec '03

31 Dec '03

Just to avoid any confusion. Can you tell me if I got this right: There are three possible ways to restict/allow communication between threads, using * Thread IDs (current L4 v4 implementation) Any thread can communicate to any thread and send any message. Access checks need to be done by the server, that might need to verify some things using another 'security' server, requiring another IPC. The IPCs itself are very fast because no table lookups are necessary to verify if the … [View More]communication is allows. However suity holes are much easier to created by buggy code that forgets to verify some accesses. Additionally the security checks are executed even slower than if they where done inside the kernel as in the other two methodes. These security checks can be done automatically using IPC redirection. This still requires an additional IPC, had some strange (unclean) quircks associated with it and I still doubt wether this methode is secure especially when used by buggy programs. * Virtual Thread Objects (possible L4 v5 implementation) Each thread has a kernel table attached to it (1) which lists the threads it can communicate to. These virtual thread objects can be grranted, mapped and unmapped just like flexpages. So when a message is received the server can be sure it is send by a thread that is mapped it's thread ID to. (1) Threads in the same address space might share the same table. * Capabilities (current EROS implementation) Capabilities are similar to Virtual Thread Objects except that they have a server defined word attached to them. I first want to make clear why the second and third methode are much better than the first: * Methode 1 is insecured when used with buggy programs. The fact simply is that most, if not all, programs are buggy. I agree with shap that the cost of a program should be measured in total resources used (dollars or additional programming time for example) and not just computational resources. * In a system that requires security the 2nd and 3rd methodes are actually faster because only a single, cimple kernel check needs to be made agisnt several complex user checks for methode 1 (is this realy true? comments please). L4 is designed to be secure anyway and is therefore already to slow for systems that don't require security, so the penalty the insecure systems woudl suffer does not apply. * Additional security benefits are that the internal thread structure is not revealed to every program running on the system and some protection against DoS attacks is offered. Now I want to make clear why capablities are much better than virtual thread objects: * The extra word does not seem to decrease performance in any way (is this true?) so it a free feature, that can be used but doesn't have to. * The server defined word will probably be used to store a pointer to some client specific data structure containing important information that needs to be access often. You might say, yeah well mbut you can calculate this address from the sender ID, but this no longer works when clients start to grant and map server objects/capabilites to eachother, because the server doesn't know about these actions, unless some complex, slow protocol is used to update the serves information. My conclusion is that Virtual Thread Objects/Capabilities are far supiror than just using Thread IDs and that the server defined word of Capabilities are very important to manage information of a server. The size of the capability should be equal to the pointer/word size of the machine. Constructive criticism is very much appreciated, Rudy Koot _________________________________________________________________ Hotmail en Messenger on the move http://www.msn.nl/communicatie/smsdiensten/hotmailsmsv2/ [View Less]

2 1

Object descriptors vs sender id
by Einar Karttunen 23 Dec '03

23 Dec '03

Hello I would like to make few notes on the recent discussion on Eros object descriptors vs the L4 sender id. Sorry if I have misunderstood parts of the discussion. The main problem is imho how can the sender know the client is entitled to use the service? Eros: - The sender just marks this information inside the descriptor. - Access check is done with a simple comparison - The state is not visible to the client - ipc is a little bit slower L4: - The state is either - visible to the … [View More]

3 2

RE: Comparing IPC and capability invocation
by Volkmar Uhlig 22 Dec '03

22 Dec '03

> -----Original Message----- > From: Jonathan S. Shapiro [mailto:shap@eros-os.org] > Sent: Thursday, December 11, 2003 9:57 AM > > By all means we should discuss, but let me attempt to clarify. > > ALL communications are invocations on objects. The only questions that > exist in principle are: > > 1. What restrictions are imposed on the TYPE of object that can be > invoked? > > 2. Is the object namespace extensible by user-mode code. That … [View More]is, > can user-mode servers present objects or interfaces that appear > to the invoker to be "first class" in the same sense that kernel > supported objects are first class. > > L4 imposes the restriction that the only invocable object type is > "process" (or in some cases thread). We only have threads, there is no notion of processes (I'm talking about V4/X.2). > L4 does *not* (today) provide means to allow a server to extend the > object name space. There is no reason, "objects" are user-managed things. Allowing extension doesn't bring you any benefit. Transparency can be implemented in a user-level library (without any overhead). How I understood your description is that you cache information about what user object types you have in the kernel. That costs you another check on the critical path. You argue that single method of invocation is a good thing--yes. We have that, it is called IPC. For all kernel objects (we have threads, AS, and memory) I don't see a benefit of a unified interface. That leads to IOCTL and that is a mess. If you want to use a generic interface (i.e. IPC) to _all_ kernel objects you can always place a protocol translation layer in between at almost no cost (threads and AS are manipulated very infrequently). This allows for optimizations you can't perform otherwise. > My first point is probably self-explanatory, so I will expand only on > the second. > > In L4, if a client wishes to perform an operation on a file, > the "name" > of the file must be passed as an argument to an IPC. The invocation is > something like: > > file_server->invoke(file-id, operation-id, ... other args ...) > > Because "file" is not a kernel-supported object, the protocol mandates > that the sender provide an additional argument in the IPC > invocation. In > the EROS philosophy, we would argue that these objects are therefore > "second class" and that this is bad for several reasons: > > 1. The invoker should not know the server identity. That should > be known only to the file object. > 2. It is difficult to transparently virtualize objects when their > invocation patterns are different. 1) Assume threads have zero costs. That means you can have one thread per object and the thread id is your identifier. 2) Assume you want to share a thread for multiple object invocations (and threads have costs > 0). The additional check you have to perform on _every_ object invocation (code for checking, table access, I and D-cache footprint etc) in EROS has probably a higher overhead than the additional parameter on the invocation which is untouched by the kernel. For concurrency (multiple worker threads) you can use LIPC in L4 so you can perform load distribution in user land. 3) Virtualizing objects is only a question of protocols. That is something _userland_ defines. So why should virtualization be difficult??? (I'm puzzled). Furthermore, how do you deal with situation where your object space is full? Is the object space local or global? We can dynamically extend and shrinl the object space (e.g. use a single bit if we have only 2 object types). > Next problem: > > The server must then run some function: > > get_permissions(sender-id, file-id) -> permissions > > to determine what operations are permitted. Note that if this > operation > is performed faithfully and correctly, it is impossible to emulate > correctly the behavior of the UNIX I_SENDFD socket operation without > many additional calls to a shared service -- the design of > the operation > makes descriptor transfer an inherently expensive operation. I would say that is a weak argument considering all the shortcomings of the POSIX API. Implementing fork within a distributed system is very expensive--so what? We know for more than 10 years that fork is broken. I will look into I_SENDFD into more detail and try to give you a satisfactory answer. > Descriptors, which *can* be used as a foundation for certain kinds of > security, suddenly become extremely inefficient because they cannot be > passed without consulting a third party. You can cache that information in user land after validation or use shared memory with the authentication server. That is what you basically do in the kernel. > The server-defined-bits portion cannot be examined by the > client. It is > provided to the server during invocation. The server can > interpret these > bits in any way desired: as an object id, as a facet id, as permission > bits, as some mix of these. > > The presence of these bits does not preclude invocation of the server > qua server; the server merely assigns to itself an arbitrarily chosen > value of "server-defined-bits" to name the server itself. So you provide an in-kernel cache for some identifiers (call it bits) which are unforgeable. How much of your register real estate do you give up for that? What when the size is exceeded? > Because these are architecturally insufficient to implement an > efficient, secure, object-based operating system. Hmm, actually that is a question of what you try to implement. What if you don't want an object-based OS? Do you incur a significant overhead with your model? I'm curious how a Linux kernel would perform on top of EROS--I could imagine that your security model has a measurable overhead. And then we have to start a discussion on generality of uKs. > Our experience has been that relying on such clients to specify the > intended operation is not robust. The flow of permissions in complex > programs is not well localized, and it is very easy to write a > subroutine designed for one purpose that does some mildly dangerous > thing and then call it (by programmer error) in the middle of some > sequence of code where care is required. > > Tying permissions to the object descriptor does not prevent the > programmer from passing the wrong descriptor, but it does help a great > deal in localizing the scope of programmer attention that is > required to resolve these problems. This sounds like you are suggesting kernel design based on bad programming habits. Are you willing to pay the overhead? We don't. - Volkmar [View Less]

4 3

Comparing IPC and capability invocation
by Jonathan S. Shapiro 21 Dec '03

21 Dec '03

[I apologize in advance for both the length and the depth of this note.] One of the long-term design differences between L4 and EROS is something I think of as the "threads vs. objects" distinction. In L4, all invocations are IPC invocations performed on thread ids. In EROS, all invocations are capability invocations performed on capability indexes. In the current EROS implementation, the capability indexes are an offset into a per-process capability table. In my opinion, the original "name … [View More]by thread-id" design in L3/L4 had two architectural issues: 1. It exposed the location of the target thread within the thread table. Because of the tight relationship between threads and tasks, this had the side effect of exposing potentially significant information about the internal structure of the recipient. It also made relocating a thread within the table challenging, because the thread's "address" was sitting in data space in every client, where one could not update it. My opinion was that the thread-id was effectively an absolute address, and that it should have been a virtual address that was decoded w.r.t. a sender-defined name space. 2. Because the thread id's and task ids were inter-related, there seemed to be a number of awkward restrictions on allocation of task structures. In particular, it was necessary to know in advance how many threads (max) were going to be required, and it was possible for fragmentation to prevent successful allocation even when the necessary number of thread entries was available. This seemed unnecessary. In addition, I thought it would be better if an address space could exist without any threads at all, and conversely if a thread could exist (though not execute) without any address space. From the EROS experience, I felt that non-process address spaces were useful. I'm not sure that threads without address spaces are useful, but I do believe that threads and address spaces are separable abstractions, and that it is good to keep them so. >From various conversations, I believe that the L4 team has addressed the second issue, and is considering a number of solutions to the first, most notably "thread address spaces". In this approach, the current thread id is replaced by an offset (or address) into the thread address space, and an application supplies this thread address instead of the thread id of the previous design. If I understand matters correctly, this idea has not yet been incorporated into the current L4 implementation but there seems to be agreement that someday it should be. I may have misunderstood, but I also believe that the power of two restriction on task allocation has been removed, and that any thread can now be associated with any task. As long as there is no operation allowing a sender to *read* the real thread id out of the thread address space, then the current plan for L4+thread-spaces would implement something very close to the future EROS design. There are two differences: 1. The current EROS design is currently expressed in terms of capability registers. We have decided that this should be replaced with a capability address space. Conceptually, this capability address space serves the same role in our architecture that the thread address space serves in Ln. 2. The elements indexed by this address space are capabilities in EROS, but thread-ids in L4. This is the heart of why I think of this as the "threads vs. objects" distinction. One way to think about this [the motivation will become clear in a moment] is that the L4 thread address space is actually a descriptor address space, but that all of the descriptors in this space are restricted to be thread descriptors. Since this appears to be the *only* remaining difference in this area of the Ln and EROS designs, I'ld like to make a case based on the EROS experience for why descriptors should be considered seriously in a future system. First, switching to descriptors should not significantly change IPC performance. A descriptor is probably a larger data structure than a thread id, but in both cases there is a load instruction at the end to place the target thread address into a register. This is true in both a thread-id design and a descriptor design. The difference would be only that the thread structure pointer might live at a different offset. Second -- and here I must draw for a moment from the EROS experience -- unifying all invocations behind a single descriptor abstraction has been incredibly useful in the EROS system. As with L4, we have a generalized invocation mechanism, but we can apply this mechanism to arbitrary objects. Introducing a generalized descriptor notion into the architecture does NOT necessarily imply a large increase in kernel size. When Leendert van Dorn and I were considering kernel design at IBM, we concluded that most of the resulting kernel descriptor types can be served by well-known user mode servers if desired. The decision about whether or not to put support in the kernel for these object types becomes purely an engineering decision. The EROS implementation chose to place these implementations in the kernel, and in one or two cases this is probably essential, but in general it is NOT necessary. The difference between a thread-id and a descriptor is that a descriptor takes the form (resource-type-code, resource-name, type-specific-data-word) where a resource-type-code is assigned for each kernel resource that is exported by means of a descriptor. Borrowing from EROS, the descriptor types that seem likely to be useful are: void -- descriptor that responds with "unknown" to all requests flexpage -- name of a flexpage thread -- a thread-id (interface to the process abstraction) object -- a particular object served by some thread In flexpages, the type-specific field holds permissions. In objects, it holds an object id. In threads, it might be unused. The EROS implementation also includes linked list pointers so that outstanding descriptors can be efficiently revoked when a resource is destroyed, but this is a detail of implementation -- other representations are possible. On revocation, outstanding descriptors become void, but we have sometimes thought that it would be better to mark change them from "type X descriptor" to "type INVALID X descriptor". This would facilitate debugging. An added word about the 'object' type may be useful, since it reflects a significant philosophical difference between L4 and EROS. In EROS, a client invokes an object. This object may be an entire server (a process) or it may be a particular object that is served by that server. In L4, the "particular object" case is customarily handled by passing an object id as an argument to the IPC operation. One problem with this is that the object id can be forged by the client. It is not entirely clear to me whether forged object ids are a serious problem in the absence of persistence, but my instinct is that they are *sometimes* a problem, and that including them is therefore desirable. The "IPC indirection" design proposed by Trent Jaeger et al. many years ago included a similar uninterpreted word. shap -- Jonathan S. Shapiro <shap(a)eros-os.org> [View Less]

5 11

Re: Comparing IPC and capability invocation
by Rudy Koot 12 Dec '03

12 Dec '03

I've been following this discussion and I first want to say that I agree that threads should be virtual objects. The cuse of thread IDs on L4 now requires eiter the receiver to check if the sender had the rights to send to it or the use of IPC redirection. Both methodes make it easy for security holes to creep into the code and are (as you correctly pointed out) even slower than using virtual objects. And if the map, grant and unmap operations can be used on them they are even more … [View More]

1 0

l4-hackers@os.inf.tu-dresden.de
by xaoveeyoyobb＠spammotel.com 12 Dec '03

12 Dec '03

1 0

Question on "mappings as cache"
by Jonathan S. Shapiro 11 Dec '03

11 Dec '03

I am trying to understand the implications of the "mapping is a cache" design argument. I suspect that this design can only be upheld if encapsulation is violated. First, however, I would like to understand the sequence of events in the following scenario: Consider a situation in which A maps some region to B B completes the receive operation, and therefore now has a copy of the mapping B is immediately preempted, before it can do any user-level book keeping about the … [View More]

5 9

2025

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

2004

2003

2002

2001

2000

1999

1998

l4-hackers December 2003