user space GUI server

[proxy]

ok, so my plan for graphics is like this:

there will be a kernel API exposing video primitives, there will be at least 3 basic functions. requestExclusiveVideoAccess, releaseExclusiveVideoAccess, and submitDisplayList.

the first 2 are so that only one app may talk to the video sub-system at a time, and the submitDisplayList is a way to batch video commands and submit them to the driver.

I want to have a single user space application which will be my main GUI server (similar to X in concept, but implemented very differently).

Here's my main question, what are the different ways I can have my other applications send/recv messages to the GUI server? I believe X uses unix domain sockets. And i suppose I could do some shared memory stufff, but that could get ugly. Is there any other clever ideas people have regarding this?

I really would like to get something going without having to create a socket like architecture just yet as that has potential to be complicated in itself.

Thought?

proxy

[Brendan]

Hi,

Here's my main question, what are the different ways I can have my other applications send/recv messages to the GUI server? I believe X uses unix domain sockets. And i suppose I could do some shared memory stufff, but that could get ugly. Is there any other clever ideas people have regarding this?

I really would like to get something going without having to create a socket like architecture just yet as that has potential to be complicated in itself.

What you need is a generic way for processes to communication with each other, or IPC. There's several approaches - files, pipes, sockets, shared memory, messaging (synchronous and/or asynchronous), etc.

For files it's done via. the virtual file system - one process appends data to the file while another process reads data from the end of the file. In this case you'd want to use temporary files in RAM to avoid disk I/O. For 2 way communication you'd use 2 seperate files. The problem here is that a file can become large (full of data that isn't needed anymore).

For pipes, normally you've got a FIFO queue where one process can write to it and another process can read from it. Again, for 2 way communication you'd use 2 pipes. Pipes are often implemented as part of the virtual file system so that normal file I/O can be used to read/write data to/from the pipe (which makes it almost the same as the above "files" option, only old data is freed).

Shared memory is simple enough to understand - a region of memory that can be read or written by several processes. One problem here is that you need to synchronize access to the shared memory - several processes writing at the same time can trash each others data. The other problem is that your "server" process ends up polling, which sucks. A solution to both of these problems is to use shared memory in conjunction with some other form of IPC. For example, a client could send "I need to send data" to the server, the server can reply with a "OK, you can send now", and the client can then put lots of data into the shared memory buffer and send "take a look at all that data" back to the server. This sounds messy, but can improve performance if your other IPC isn't suitable for large amounts of data (e.g. video textures, bitmaps, etc). Shared memory can also be used to implement other forms of IPC (for e.g. you could implement pipes on top of shared memory, perhaps as part of a C library).

Then there's messaging, which can be done in a number of ways. It can have connections (where you need to establish a communication channel first) or it can be connectionless (where anyone can always send anything to anyone else). A message might be a fixed size (e.g. 4 dwords) or it might be variable size (up to some limit). Also, on some systems "message ports" are allocated when they are needed, while on others they are automatically assigned. For e.g. on my OS every thread always has one message port (where messagePortID = threadID) - it's impossible for a thread to have 2 or more message ports, and impossible for a thread to have no message ports.

For all forms of IPC, you'd want to establish rules for how it interacts with the scheduler. Does sending data to a higher priority task cause an immediate task switch or not (or only sometimes?), and can a task wait for data so that it doesn't consume any CPU time until it receives something? Can it set a time-out so that it doesn't wait forever if nothing is received? What if a task is blocked waiting for IPC data and the kernel wants to send it something - is there a seperate system for this (e.g. signals in POSIX) or does the kernel send IPC instead?

You could implement several forms of IPC so that programmers can use whichever type they think is most appropriate for their needs (common for *NIX/POSIX). The opposite approach is also possible - choose one method of IPC and then design the entire OS specifically for it (common for micro-kernels).


Cheers,

Brendan

[mystran]

This reminds me:

One thing that I've always felt very weakly represented in OSFAQ, and not that well represented elsewhere either, is the tons of different ways to do messaging.

I wonder, if somebody (don't look at me) should try to compose some kind of collection of "All possible and impossible messaging methods".

I mean, simply saying "Messaging" really says very little, beyond the use of messages, about the method. Some forms of messaging aren't two different from each other, while some forms at totally incompatible with other types (other than general messaging allowing the implementation of other types of messaging, ofcourse).

... your thoughts?

[Brendan]

Hi,

... your thoughts?

It doesn't sound too hard to list the possible options:

• - connectionless or with connections
  - synchronous, asynchronous or both
  - fixed size or variable sized messages
  - with or without message port (or exchange, mailbox, whatever) allocation
  - if task switches occur when sending a message (always, never, if the receiver is higher priority)
  - prioritized or un-prioritized messages

Everything else is implementation details - whether it's implemented on top of some other form of IPC or not, if there's standardized messaging protocols, if a message port can be given a public name, the message size (or minimum/maximum message size), etc.

I can't think of any impossible way of combining these options (even though some combinations don't make much sense). One of the biggest factors is whether there's "message queues" or not, as some of these options are impossible without message queues (asynchronous, task switches don't always happen when sending a message, prioritized messages).

For me it'd be connectionless asynchronous messaging, with variable sized messages, without message port allocation, where thread switches occur when a message is sent to a higher priority thread and messages aren't prioritized.

The tricky part would be giving each type of messaging a name so that people know what you're talking about. The only one I can think of is "Rendevouz Messaging" - synchronous messaging, typically with fixed size small messages, where task switches always occur when a message is sent and messages aren't prioritized.


Cheers,

Brendan

[proxy]

I actually think that i am going to go with a message system for my main IPC mechanism. The way i plan on having it work is like this:

so far i have thought of a basic API like this:

Code: Select all

msg_listen(int port); // enables a process to recieve a message on a given port number

msg_send(pid_t pid, int port, const void *buf, size_t len); // sends a message

msg_recv(int port, void *buf, size_t len); // recieves a message

msg_close(int port); // disables reception of a message on a given port

recv will be blocking, (will block until some data arrives, but may return less than buffer size requested)

the reason why i have this design in mind is because i think it will be very easy to build IP protocols ontop of it when I decide to start going that route, network ports will just be mapped to process message ports, and so forth.

you guys see any gapping holes in the thought process here?

proxy

[mystran]

Everything else is implementation details - whether it's implemented on top of some other form of IPC or not, if there's standardized messaging protocols, if a message port can be given a public name, the message size (or minimum/maximum message size), etc.

I don't agree. For example, whether message ports are publicly discoverable, whether they can transfer handles to message ports, and so on have large enough consequences that I wouldn't write them off as "implementation details."

I can't think of any impossible way of combining these options (even though some combinations don't make much sense). One of the biggest factors is whether there's "message queues" or not, as some of these options are impossible without message queues (asynchronous, task switches don't always happen when sending a message, prioritized messages).

Funny. Coyotos doesn't really have queues. It does however use asynchronous messaging. If I understand the whole mess correctly, you have so called "first-calls receive buffers" with notifications (using scheduler activations) when a message is received. Basicly, it seems to be able to do asynchronous messaging, without queues, and with single copy.

For me it'd be connectionless asynchronous messaging, with variable sized messages, without message port allocation, where thread switches occur when a message is sent to a higher priority thread and messages aren't prioritized.

Well, I currently have "connectionless" asynchronous messages, sent using unforgeable object handles (acting as capabilities). They are queued, but thread switches can occur if a higher priority thread is unblocked because of the message.

I am possibly going to implement a DMA-lookalike long-message transfer on top of that, to avoid double copying.... but no details yet.

In any case, I'm becoming even more confident that writing an overview might be a good idea. I think I'm going to try come up with something next week (or maybe today, I don't know).

[Brendan]

Hi,

Everything else is implementation details - whether it's implemented on top of some other form of IPC or not, if there's standardized messaging protocols, if a message port can be given a public name, the message size (or minimum/maximum message size), etc.

I don't agree. For example, whether message ports are publicly discoverable, whether they can transfer handles to message ports, and so on have large enough consequences that I wouldn't write them off as "implementation details."

In all cases, if the OS itself doesn't support giving a message port a public name then a reference to the message port (e.g. the message port number) could be stored in a publicly accessable file, so that other tasks can use a file name to obtain the message port number. IMHO this means that it doesn't really matter much if the OS directly supports named message ports or not.

For systems without "message port allocation" (i.e. where every task always has one message port), allowing message port handles to be transferred doesn't make much sense. For other systems you have a good point. This gives 3 "message port ownership" options - every task always has one message port, any task can have none or more message ports where message ports can't be transferred, or any task can have none or more message ports where message ports can be transferred.

I guess there's also differences in where security is enforced. Some systems have kernel enforced security (where you must have permission to send to someone else - e.g. Minix 3), and other systems allow anyone to send anything to anyone else (where the receiver does any security checks in user-space - e.g. Mine).

There's other difference I've overlooked - whether message data is copied or moved, and if it needs to be in a special area or not.

For me, there's a special part of the address space called the "message buffer" where all message data is sent from or received. Message data is always moved and not copied, so that after a message is sent the sender's message buffer always contains nothing. This means that for larger messages I can move page table entries or page directory entries. For e.g. for a 32 MB message I'd move 8 page directory entries (or 32 bytes) from the sender's page directory to the receiver's message queue, and when the message is received those 32 bytes are moved from the receiver's message queue into the receiver's page directory.

Funny. Coyotos doesn't really have queues. It does however use asynchronous messaging. If I understand the whole mess correctly, you have so called "first-calls receive buffers" with notifications (using scheduler activations) when a message is received. Basicly, it seems to be able to do asynchronous messaging, without queues, and with single copy.

This is a matter of perspective - Coyotos (from what I can tell) uses a message queue that is only capable of queueing one message, called a "First-Class Receive Buffer". From this web page, under the description of Stateful Messages:
"A stateful message is one where the sender defines the message payload and the receiver specifies (via a stateful FCRB) the location(s) in the receiver address space where the payload should be delivered. A stateful receive FCRB may be either pending or delivered. A send operation on a stateful FCRB will not make progress until that FCRB becomes pending. On completion, it causes the FCRB state to transition from pending to delivered. The receiver must explicitly reset the FCRB state before subsequent attempts to send on that FCRB will make progress. This ensures that the received message payload cannot be overwritten by successive senders before processing."

IMHO this makes it "limitedly asynchronous", in that if you try to send multiple messages to the same receiver you will block due to the receiver's limited message queue depth.

I've ignored their "Idempotent Messages" because to me they look like a bitmap or set of flags, where "sending" means setting a flag and "receiving" means checking if the flag is set and clearing it (it reminds me of the way *NIX signal handling is usually implemented, and doesn't seem like messaging at all as no data is actually transferred).

I must admit I didn't read their pages too much - it made my head hurt (it's like the aim of their project is to make things as confusing as possible by only implementing half of everything and making user-space code make up for the missing parts).


Cheers,

Brendan

[mystran]

Yeah well, in other parts of Coyotos docs, it says "asynchronous receive" which is what it's really designed to do. The problem it addresses is a server servicing thousands of clients: with FCRB it can supposedly:

1) take a request
2) send a subrequest
3) continue while the subrequest completes

without needing a separate thread for each and every client, which is what traditional synchronous IPC would need (and where it breaks down in real world).

In any case, technically I do not have message port allocation, yet it still makes sense to copy (or well, move, copies require explicitly asking for one) handles: there is exactly one message queue (or port) per thread, but a handle contains both the thread and some protected payload. So while the port is the same, two handles to it are not usually equal.

My system is strong in only letting you talk to someone you have handle to. You can't even talk to kernel services without a proper handle. Now, the problem with allowing sends to anyone, is that it falls prey to the so called shatter attack of Windows very easily.

The original version injected code with WM_SETTEXT to priviledged windows, then sent WM_TIMER to trigger execution of that. Worked because default handlers would allow it even when sent from a window of different user, and you could enumerate window handles to find a suitable one (like one of Winlogon's). I guess it still works. (Look, I'm on topic, I'm talking about GUI messages.)

Even if you were more careful than that, you still risk letting totally unrelated programs exploit bugs in your code, where the stronger model would automatically check access first (ACLs?), and even stronger model wouldn't let you name anything you don't have access to (proper capabilities).

[Brendan]

Hi,

In any case, technically I do not have message port allocation, yet it still makes sense to copy (or well, move, copies require explicitly asking for one) handles: there is exactly one message queue (or port) per thread, but a handle contains both the thread and some protected payload. So while the port is the same, two handles to it are not usually equal.

My system is strong in only letting you talk to someone you have handle to. You can't even talk to kernel services without a proper handle. Now, the problem with allowing sends to anyone, is that it falls prey to the so called shatter attack of Windows very easily.

The original version injected code with WM_SETTEXT to priviledged windows, then sent WM_TIMER to trigger execution of that. Worked because default handlers would allow it even when sent from a window of different user, and you could enumerate window handles to find a suitable one (like one of Winlogon's). I guess it still works. (Look, I'm on topic, I'm talking about GUI messages.)

IMHO the main problem with kernel enforced messaging security is that it's either limiting, slow or coarse grained.

For example, Minix 3 uses a per process bit mask where each "allowed/not allowed" flag represents each possible receiving process. This is fast, but the bit mask is limited to N bits, which limits the entire OS to a total of N processes (I can't remember what N actually is - I think it's 256 bits, which is complete crap considering that most modern OS's can run tens of thousands of processes). It's also coarse grained - you can't say that some messages can be sent by anyone, some messages can be sent if you register yourself first, some messages can only be sent by one process, some messages can be sent by some threads but not others, etc.

To avoid having limited and/or coarse grained security, you need very complex security mechanisms (i.e. it needs to be slow and/or consume a lot of memory).

By shifting the security to user space (i.e. making the receiver do it's own security checking) it can be as fine grained as necessary and customized for the specific purpose without unnecessary complexity. This does mean that each receiver could have security holes, but coarse grained security is also likely to have security holes.

For Windows, if you had a condom that was designed by Microsoft would you use it? At a minimum I'd see if it was capable of holding water and then put it on my finger to find out if there was anything sharp. Unfortunately operating systems aren't as easy to check... ::)


Cheers,

Brendan

[Colonel Kernel]

Sorry if this is straying a bit offtopic, but I had to jump on this one...

without needing a separate thread for each and every client, which is what traditional synchronous IPC would need (and where it breaks down in real world).

This looks like a straw man to me. This is simply not how servers are designed in the real world. Normally a single thread per CPU would accept all incoming requests and put them on a queue. The server would have a pool of worker threads that pick up requests from that queue and fulfill them. The size of this pool would depend on the server's purpose. For CPU-bound servers, the pool should probably have as many threads as there are CPUs (or maybe a few more), while for I/O-bound servers, the pool should be a lot bigger. I/O-bound in this case can either mean delegating (synchronously) to another server (e.g. -- file system to disk driver), or waiting for an interrupt (e.g. -- the disk driver itself).

This pattern I've described is extremely common in servers of all kinds. It's not hard to imagine it being used in OSes such as QNX for example, which is based on synchronous IPC (and has been commercially successful for something like 23 years... sounds quite "real world" to me).

One thing that does jump out about this approach is obviously the extra context switching involved to service a request. IMO, this is a more compelling reason to favour asynchronous IPC. But let's not kid ourselves about how servers are designed "in the real world"... system designers have more sense than that.

[nick8325]

IMHO the main problem with kernel enforced messaging security is that it's either limiting, slow or coarse grained.

For example, Minix 3 uses a per process bit mask where each "allowed/not allowed" flag represents each possible receiving process. This is fast, but the bit mask is limited to N bits, which limits the entire OS to a total of N processes (I can't remember what N actually is - I think it's 256 bits, which is complete crap considering that most modern OS's can run tens of thousands of processes). It's also coarse grained - you can't say that some messages can be sent by anyone, some messages can be sent if you register yourself first, some messages can only be sent by one process, some messages can be sent by some threads but not others, etc.

To avoid having limited and/or coarse grained security, you need very complex security mechanisms (i.e. it needs to be slow and/or consume a lot of memory).

I don't think kernel-mode security needs to be as complex as you say. My toy kernel uses capability-based security, and IPC is fast-ish (~100 clocks so far, as I use a weird hack for it, but that doesn't matter here) and doesn't take up much memory. Here's the idea:

• Each process has a table of capabilities. A capability is (more or less) a pointer to a thread, and an object ID. It's meant to represent an object. The table is stored in kernel-mode and not directly accessible to user-mode code.
• Instead of asking to send a message to a thread ID, the sender asks to send a message to a capability (by giving an index into the capability table). The kernel looks up the thread (just an array lookup), and passes the object ID and message along to the receiver.
• Messages can transfer capabilities as well as data. In other words, if a process can access an object, it can give another process permission to access the object by sending it a capability to the object in a message.
• There's no way to forge capabilities (as the capability table is protected). You can only get a capability by receiving it from some other process.

There, that's the whole security model

The rest is left to user mode, which is organised like this:

• Servers make a capability for each object they have. For example, a console server with multiple virtual consoles will make a capability for each virtual console. In that way security can still be fine-grained: a process with a capability for one console won't automatically be able to use another.
• Each process by convention starts with one capability, a name server. If you send the name of a service to a name server, it will return a capability to that service. It's up to the parent process to give the child a name server. The name server will normally have capabilities for all sorts of things, such as the file system root, network server, ...

This means that most servers can forget about security: they can just give out a capability to some init-process and rely on that to only distribute capabilities to authorised processes. The security is still fine-grained, because the object ID is unforgeable.

As the name server capability is just an ordinary capability, processes which want to can play all sorts of tricks by giving the child processes unusual capabilities, without any help from the kernel. For example:

• You could stop a child process from using the file system by not giving it a capability for the file system root. Or you could implement chroot() by giving it a capability for some other directory as the root.
• You could intercept all the messages your child sends (and so write something like systrace) by giving it capabilities for you instead of for the normal servers. Then you would forward messages from your child on whenever you got them.

Other kernel resources also have capabilities. For example, to set the priority of a thread you'd need a capability for it. There could be capabilities for processes and memory regions and things like that, and capabilities for privileged things (such as a disable-interrupts capability). That means that the kernel can forget about security policies, too, and user mode can organise security of kernel things.

I hope that that's a counterexample to your assertion that "the main problem with kernel enforced messaging security is that it's either limiting, slow or coarse grained"

It also leads into stranger areas - e.g. the kernel can see what processes can talk to what others, so you could add a type system to prevent capability cycles (i.e. potential deadlocks). But I'm not too sure how all that might work yet

[mystran]

[*]Each process has a table of capabilities. A capability is (more or less) a pointer to a thread, and an object ID. It's meant to represent an object. The table is stored in kernel-mode and not directly accessible to user-mode code.

This is what I have too. As it is, after Hurd people tried to build their system over L4, they noticed that wasting the few cycles in IPC to do capability validation will translate into lots of overhead reduction in userspace. Hence, L4.sec, the status which I must confess I haven't followed really.

In any case, how is userspace supposed to perform validation anyway? Either you try to make thread IDs unique over "sufficiently long time" (like original L4) and implement capability system based on that, which is hairy at best, or you revert to something like ACLs, which without stateful connections introduce tons of overhead, and which are pain to manage if you try to enforce strict POLA.

[*]Instead of asking to send a message to a thread ID, the sender asks to send a message to a capability (by giving an index into the capability table). The kernel looks up the thread (just an array lookup), and passes the object ID and message along to the receiver.

Yep. This means that the protected payload (or objectId) carries not only state but access priviledges as well. If it's unforgeable, access is unforgeable as well. While you can think of thread-id/object-id being a secure pointer to an interface of an object, you can also think of it as an opaque remote continuation, or a lot of other interesting things...

Btw, this isn't too different from using session cookies in web applications (session ID is little different from object ID), except it's much less overhead (just fetch two pointers from a table). Nobody complains that session IDs won't allow fine grained security; they do.

Ofcourse capabilities can be made fully unforgeable on local machine.

[*]Messages can transfer capabilities as well as data. In other words, if a process can access an object, it can give another process permission to access the object by sending it a capability to the object in a message.

Yes, and this is proven to be sufficient to implement any kind of access control whatsoever. So it is both more lightweight and more general than most other solutions. Ofcourse capabilities make almost no sense if you don't do this.

As for copying capabilities, my capability move (no copies in general case) invalidates the capability from sender, by writing a single pointer, and saves the capability as part of the message (two pointers). So it's about as fast as sending two pointers, too.

I hope that that's a counterexample to your assertion that "the main problem with kernel enforced messaging security is that it's either limiting, slow or coarse grained"

I'd personally like hear of single other option that is:

- as fast: remember, two pointers fetched.
- as fine grained: you can easily enumerate each and every method somebody is allowed to call
- as secure: fine grained POLA is enforceable mostly even in presence of bugs.
- as general: proven to be universal (as in equivalent in power to Turing/Lambda....)

One example that you don't mention, but which my system allows, is doing system virtualization with little extra effort: in my system every process gets one capability too ("master" capability), but this capability is used to access all kernel services as well.

So any process can implement proxies for kernel services, and start other processes (provided it's own master allows), so that running a virtual copy of the system under system is just a matter of writing a suitable server. The processes running within the virtualized system can't (theoretically) tell whether they are running in a virtual system, and still might have direct access to some subdirectory (or well, subnamespace) of the global namespace, avoiding overhead there.

Now, ofcourse the principal problem is how to maintain the capability table, when the number of capabilities per process grows. But this is little different from maintaining a list of file descriptors in a Unix process...

Oh, and unix-domain datagram sockets could be considered a capability system (they can transfer filedescriptors too) if other IPC mechanism wouldn't exist in Unix. I'm going to write an emulation library on top of those to debug servers on top of Unix at some point, btw.

---

One thing I'm unsure about: should messaging be symmetric or asymmetric. If client/server model is assumed anyway, then would it make sense to support that directly, instead of a general P2P mechanism (which can't take some shortcuts).

[Brendan]

Hi,

I hope that that's a counterexample to your assertion that "the main problem with kernel enforced messaging security is that it's either limiting, slow or coarse grained"

Maybe...

Imagine I've got a single threaded "keyboard macro" utility. The keyboard driver/process can send a "key was pressed" message to it and the GUI can send a "set new keyboard shortcut" message to it, but the GUI can't send a "key was pressed" message and the keyboard driver can't send a "set new keyboard shortcut" message. In addition, if the keyboard driver/process is a PS/2 driver and has a seperate thread for handling the PS/2 mouse, then this second thread can't send anything (even though it's part of the same process). Also, all threads might be allowed to send a "who are you" message, and any kernel thread might be able to send some messages (shutdown, restart, etc).

Unfortunately, "fine grained" in this situation means a per-thread per-message-type bitmask. There's 2^32 possible "message function numbers" for my messaging that identify the type of message to the receiver, and there's 2^48 possible senders (thread IDs). This adds up to a 2^80 bit mask for each thread to determine which threads can send which messages (it's larger than any 64 bit CPU can handle, but it would be quick).

There's ways of doing it without the huge bitmask, but that's where things get messy...


Cheers,

Brendan

[Brendan]

Hi,

In any case, how is userspace supposed to perform validation anyway? Either you try to make thread IDs unique over "sufficiently long time" (like original L4) and implement capability system based on that, which is hairy at best, or you revert to something like ACLs, which without stateful connections introduce tons of overhead, and which are pain to manage if you try to enforce strict POLA.

Code: Select all

    for(;;) {
        while( getMessage(&senderID, &length) != OK) { }
        messageID = (u32 *)messageBuffer;

        switch(messageID) {
            case HELLO:
                do_hello();
                break;
            case FOO:
                if(senderID == someone_I_trust) {
                    do_foo();
                }
                break;
            case BAR:
                if( (senderID == someone_I_trust) || (senderID == someone_I_know) ) {
                    do_bar();
                }
                break;
            case WOOT:
                if(senderID == someone_I_trust) {
                    if(first_day_of_month() == YES) {
                        do_woot_day1();
                    } else {
                        add_to_log("Someone I trust tried to WOOT at the wrong time!\n");
                    }
                }
                break;
            case YAY:
                if(senderID == someone_I_trust) {
                    do_yay(0);
                } else if(senderID == someone_I_know) {
                    do_yay(1);
                } else {
                    add_to_log("Warning: YAY received from unknown source.\n");
                }
                break;
            case SHUTDOWN:
                if( senderID == KERNEL) exit(0);
                break;
        }
    }

Can all of the above security checks be done by the kernel, or do you propose coarse grained security with more security in userspace? In the latter case, why are different security checks being done in different places?


Cheers,

Brendan

[mystran]

Oh, no... you don't do capabilities with bitmaps.

Such implementation doesn't even satisfy capability security; in a proper capability system, all you can tell about a capability is whether you have it, and how it responds to invocations. Normally there's also some way to compare two capabilities for identity (it's nasty to do without special support).

Specifically, you do NOT have capability system (you just have a fine-grained ACL, and yes, I'm ignoring some complications) if a process tells what service it wants to access, and system then checks whether this is allowed. In capability system, the process tells which capability it wants to use, and the ownership of the capability (which names the actual resouce) automatically implies access.

---

I will assume in the following that capabilities are per process, because that's most common. You can do per-thread too, if you feel like it.

The normal way to do capabilities, is to extend the concept of a process to contain not only a memory address space, but also a capability address space. It can internally be anything from a constant size per-process table, to kernel-accessible part of the process address space.

This capability address space is really nothing but a table of capabilities held by the process. If a process holds two capabilities, it has two non-null entries in it's capability space.

To invoke a capability, you simply index into this capability space, fetching the capability itself (containing whatever data you need, I personally have just target-thread and protected-payload the size of a pointer). Then you use this capability to perform the invocation.

So basicly, instead of doing:

target = userspecified_target
method = userspecified_method

you do:

capability = process->capspace[userspecified_index]
if (capability == null_capability) fail;
target = capability->target
method = capability->method

The only real problem introduces then, is allocating entries within the capability table. But if capabilities are large enough to contain pointer, and have at least one bit to use for purposes of marking them "null", then you can keep a freelist in the data that would normally be used by the capability.

Now userspace never sees the capabilities, instead it only sees indexes into capspace. It's conceptually little different from using pointers to memory. Using part of the memory space as holder for capability space is particularly nice idea (I like it anyway) because it means virtual memory can help with resizing, and even do bounds checking (assuming we check for maximum allowable index, or prevent it's representation by using only the number of bits that we can provide space for, or whatever).

Oh, and it's normal to replace method by either interfaces, or sender side object implementing some interface. This doesn't really make it any more fine-grained since you can still have interfaces that only implement a single method. Some systems finally replace "thread" by "endpoint" to allow multiplexing of receives.

Notice that "capability" is not conceptually an "access right"; it's a "way to name a method or object". So the best way to think of a capability is as a "secure pointer". In a capability system, without a capability, you can't refer to an object, unless you have another capability to an object that implements a namespace that can be used to lookup the object. It's very similar to how you can't magically come up with a pointer in Java.

---

PS: could some moderator please split this thread? I could start a new thread, but experience tells me that discussion (if any) will continue in the old one anyway.