l4-hackers

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

2827 discussions

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

01 Jan '04

Some comments and questions to about 5 different e-mails: ===== Rudy Some of Volkmar's arguments are based on the fact that L4 is a general purpose microkernel, I think the discussion would be more useful if we look at how a microkernel with the purpose of running a capability based system on top, should be design. Leaving the question wheter those capabilities should be implemented at kernel-level or user-level open. ===== Rudy Any form of IPC in which the decission to allow or disallow a thread to send a message to another thread is vulnerable to a DoS attack. If the decission is mad by the kernel the IPC can be canceled immediately, but if it is made at user level another thread is blocked for a small amount of time. ===== Shap > 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. Sorry, but you still owe me an example of a situation in which revealing the sender-id actually breaks the security of the system. The only thing I could think of was that it might reveal some details about the internal structure of an application, but if the system is secure that information hasn't got much use to a malicious program or user. I really think this is an important point. If revealing the sender-id is indeed a violation of security, there wouldn't be a need to discuss wheter or not thread-spaces need to be implemented. They just have to. > c) More specifically, any microkernel that requires checks based > on sender-id is entirely unsuitable as a platform for EROS-NG. Why? ===== Volkmar >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%. I believe these costs are exagerated. To convert a capability into sender-id a simple table lookup can be used. This requires a single TLB entry and a single L2 cache line (worst case). If IPC is frequent, which is the case in which you want high performance, the TLB entry is very likely to be present and probably even the L2 cache line. This is supported by your own description how access checks are done at user level (although this is actually the reverse as you point out, the methode stays the same): >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. ===== Volkmar >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. Sorry, but I do not see how the version part could be used as the server defined word. You can't have multiple versions (read server defined words) of the same thread-id at the same time. ===== Volkmar >- local data structures--or do you want to share your cap-tables on NUMA >systems between processors? How do you plan to memory-manage those? I generaly don't worry too much about performance as long as it scales wth processor speed/count. This argument is indeed a sane one. However I do believe it is possible to use the techiques to gain better performance used at user-level can also be applied to a kernel-level methode. This does bring up another question. How do you memory manage TCBs in L4 on NUMA systems? ===== Volkmar >That is exactly the point. If you add that feature to the kernel you >pay on _every_ system, even if it does not need any security mechansims >at all (or only very rudimentary). Hence, moving it to user land >eliminates it from the critical path and makes other scenarios faster >(without, from my perspective, massively hurting systems which need and >want such security models). Whoch person with a sane mind would want to implement an unsecure operating system on top of a microkernel? That's just not a smart thing to do. The only reason microkernels still exists is because they offermore security and are more flexible. And unsecure systems are also systems that wnat maximum performance (so they don't want to run on top of a microkernel) and for that same reson don't need the flexibility. Unsecure operating systems no longer run on servers, workstations and dektops. They are only used for embedded systems, and those are unlikely to run ontop of L4. -- Rudy Koot _________________________________________________________________ Hotmail en Messenger on the move http://www.msn.nl/communicatie/smsdiensten/hotmailsmsv2/

1 0

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 microkernel, but > of operating system policy). That is exactly the point. If you add that feature to the kernel you pay on _every_ system, even if it does not need any security mechansims at all (or only very rudimentary). Hence, moving it to user land eliminates it from the critical path and makes other scenarios faster (without, from my perspective, massively hurting systems which need and want such security models). > 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] And you forgot all the TLB entries you need. When moving it to user land you are able to optimize the lookups by: - clever choosing identifiers (your identifier space is unlimited and can be as small as zero bits) - efficient and combined lookup strategies (e.g. a file descriptor can contain the filepos and security identifiers) - combined calls, i.e. accessing multiple identifiers at once (write to n files at a time, multicast) - local data structures--or do you want to share your cap-tables on NUMA systems between processors? How do you plan to memory-manage those? - Volkmar

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 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/

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 client - the client can mutate it -> expensive checking - the client can pass it to others without supervision - stored inside a non-related thread - instead of two ipc operations we need three (C->S->C becomes C->store-thread->S->C) - stored inside server (more complexity, granting permissions is hard) - All servers need to store client state. - Upon each request we typically need a hash lookup - Clients need to communicate passing descriptors to the server - The pager adds a prefix scheme does not really help as the server does not necessarily trust the clients pager. The following come into mind as problem cases: - A client using thread pool - A permission for all children of a thread (or capabilities in general) Also the Eros model seems to map better to a distributed enviroment. In L4 one would need to allocate one thread per remote client/thread/set of permissions while in the Eros model just hold different capabilities. Modelling L4 with Eros - The server uses a word of data in the descriptor - The kernel fills it with the caller-id (needs hacking) Modelling Eros with L4 - This seems quite difficult to archive without additional lookups. - How can one build a *safe* mechanism on top of L4? - All API based approaches fail because malicious clients can send handcrafted messages. - Einar Karttunen

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 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

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 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>

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 flexible than the current implementaion. I'm however still doubting wherer EROS capabilities are necessary, because I believe the arguments you have given are entierly correct >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 ...) >In EROS, the corresponding invocation would be: > > file_capability->invoke(operation-id, ... other args ...) While this might be true at the lowest level, high level abstactions will geneally hide this fact from you, making this only an aestatic argument unless you can tell me why one of them is technically better/safer. And I think the examples you give here have been given in a form that is more favorable for de EROS case. The true inkovations would normally look more like this: L4: invoke(file_server_thread, file_id, operation_id, other_args) EROS: invoke(file_capability, operation_id, other_args) Again I want to stress that this is normally hidden by the high level language interface. Some interessting thing can also be done with alternative designs. For example the open call op the file_server creates a new thread that handles the calls to that file. The calls would now look like this: L4: invoke(file_thread, operation_id, other_args) EROS: invoke(file_capability, operation_id, other_args) Looks pretty similar doesn't it. The difference is now that in L4 the messages are send to a collection of threads while in EROS it is only one thread. -- Rudy Koot _________________________________________________________________ Play online games with your friends with MSN Messenger http://messenger.msn.nl/

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 mapping ... other stuff runs ... kernel runs out of mapping cache space, chooses to evict the mapping just received by B ... other stuff runs ... B attempts to reference the region that it believes should be mapped, and page faults. Can someone explain the process by which B is able to get the mapping reconstructed? shap

5 9

RE: Naive question about grant/map
by Volkmar Uhlig 11 Dec '03

11 Dec '03

> -----Original Message----- > From: Kevin Elphinstone > Sent: Wednesday, December 10, 2003 8:57 PM > To: 'Jonathan S. Shapiro' > Cc: 'L4 Hackers List' > Subject: RE: Naive question about grant/map > > Just a small, but important point relating to the statement below. > > The L4 mapping database is NOT strictly a cache, but it can be used to > implement cache-like behaviour which is usually what is done in most > systems. Kernel mappings are a dynamic subset of things defined at > user-level. However, in kernel mapping can be used to > indirectly define an address space or region of an address space > (if, for example, you what to avoid faults). I.e. it can equal > or be a superset of what is defined at user-level. However, doing > so requires carefully crafted and coordinated pager behaviour/protocol. > > You can term it a (large) cache with mechanisms to control > its population, but it is not exactly a "cache" in the terms usual > sense of the word. This also depends on your point of view. Your statement that the kernel mapping can be a superset of user-level pagers is wrong. The user-level pagers have full knowledge about the replacement policy (since it is implemented in user land via map and unmap) and therefore can rely on the fact that the kernel won't replace entries in the cache. If it would be a superset then the kernel would have to enter values itself. - Volkmar

2 1

Jump to page:

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