OSDev.org

I've just gotten an ELF program to run in a separate address space to the rest of the kernel (finally, I'm getting somewhere ) but now want to implement message passing so that I can start testing my driver interface.

Currently this is my idea:

In the process structure, there is a linked list in which a queue of messages sits. When the process calls 'recv', the kernel checks to see if there are any messages on the queue. If so, it takes the first one (FIFO) and sends it back to the process. However, if there aren't any messages, it waits until a message comes. Processes that are waiting for a message are put into a special state which allows the kernel to choose when to wake up the process.

The only problem I have here is using the kernel heap for the message queue, which could create security issues.

Any ideas?

just brainstorming here:

- if you kernel has access to the thread memory. it can do a copy from one thread to another thread. As the message is defined in the thread it should be ok and have no kernel memory.
- if you would make the message queue in readonly memory for a thread. it can process the message(s) from that queue and flush them afterwards by a single kernel call saving some context switches.

This is a bit of a brain dump of an idea I had, but have yet to implement:

There is no need to copy messages around if you use address mapping. An API could be:

Message* msg = CreateMessage(); // asks kernel for writable mem block
... // write your message here
SendMessage(ProcID receiver, Message* msg); // async send

The kernel could unmap message from sender address space and map it into receivers address space - no copying.

at the recieving end you would have

Message* msg = Revcieve();
... // read the message

One problem is that a message has to be at least 1 page of mem. But if you were dealing with images or audio the speed advantage would be great.

You have choices about when message ownership changes and who is repsonsible for destroying etc. In fact you could use a rotating series of messages if you are streaming data. On Dr Dobbs web site there was an atricle about using 3 buffers to transfer data and minimize locking

I define a one page long message buffer per process (although it can be larger if I wish) which is mapped at PL3 into the process. Therefore reading messages doesn't involve a trip to the kernel and back, but is implemented as a user library function. Sending messages does, and there's a bit of overhead with mapping the receiving buffer into the sending process' address space.

Mark139 wrote:There is no need to copy messages around if you use address mapping. An API could be:

Message* msg = CreateMessage(); // asks kernel for writable mem block
... // write your message here
SendMessage(ProcID receiver, Message* msg); // async send

The kernel could unmap message from sender address space and map it into receivers address space - no copying.

The problem there is that *msg is (I presume) just a piece of data allocated on the heap. If you map the entire page(s) it occupies to another process, you might end up sending some sensitive data to the other process. Shared memory is useful for larger messages, sent only between two processes (i.e. not a general catch-all message buffer).

You also need to think about how you organise your message buffer. I assume you want it in FIFO style, so you could use a queue, but then you run into problems with all the entries being scattered among various pages (unless you're careful). I find a circular buffer works quite well. You basically maintain a read and a write pointer into the buffer. Initially, read = write = start of buffer. When you want to write, you calculate maximum available message space (from write up to read, possibly wrapping around the end of the buffer) and then write to it (again wrapping if necessary), then update the pointer (with mutual exclusion of course). Reading involves getting the memory at read pointer then updating the pointer. You can quickly check if a message is waiting by comparing the two pointers. If they are equal then there is no message waiting.

kernel side send message
user side receive message
These functions are very badly written from a concurrency point of view, but they demonstrate the ipc functions. I will alter them when I get a chance. I'm currently redesigning my kernel for another matter, so these have been forgotten for a bit.

Regards,
John

The idea is to use a ring buffer. "A circular buffer or ring buffer is a data structure that uses a single, fixed-size buffer as if it were connected end-to-end. This structure lends itself easily to buffering data streams." [1]. The communication between two entities can by unidirectional or bidirectional. A ring buffer is considered a channel which is governed by a standard that dictates that each channel only support communication in one one particular direction. Each thread is a individual entity, and each process excluding the threads it contains is a individual entity which can be control a particular thread. To help protect this communication mechanism from malicious executable code there are some rules. These rules include not allowing duplicate directional channel instancing or hosting between two identical entities, providing entity channels instead of a global/one/single channel, and checking of the length field in the channel header along with the length in each message header. Priority of messages is provided on a entity level, but not message type which would be implemented outside the realm of this explanation.

The general implementation for a ring buffer header is as: The length field designates the length of the buffer, and once you go past this length you wrap around back to offset zero in the buffer and the process will repeat indefinitely. The used field designates the amount in bytes of all the remaining messages. The write field holds a byte index inside the buffer in which a new message may be written with out overwriting pending data in the buffer (written previously, but not read or removed from the buffer). The read field holds a byte index inside the buffer in which the next pending message is awaiting. The write byte index must never exceed the read byte index or you risk overwriting messages which are currently being read.

This structure stands against the abuse of concurrent access by only allowing the sending side to modify the write field. While, the receiving side only modified the read field. This produces a natural lock free scenario in which: A reads write, and writes read and B reads read, and write write. Also A subtracts the length of each read messages from used, while B adds the length of each written message from used which prevents the empty and full problem when using ring buffers.

The ring buffer is created as a region of memory shared between two memory contexts or the same memory context in special circumstances (but not normal ones) so that each thread has direct memory access to modifying the buffer with out invoking the kernel.

A entity shall be an individual thread of a process, or the process it's self. A thread may act as an entity while it also acts as the pseudo entity for the process. Multiple threads acting as an pseudo entity for the process must perform their own negotiating, mutual exclusion, locking, or any and all of the said when modifying rings instanced or hosting by the process as a individual entity.

Each ring buffer shall be considered a channel which is unidirectional (messages only go one direction). Bi-directional communication is performed by using two channels (one for each direction).

A entity shall instance or host no duplicate channels. A duplicate channel is when two or more channels exist between the same two entities in the same direction. This is to prevent a denial of service attack by malicious code creating thousands of identical channels.

A entity shall ensure that the channel header (and the each of the message header) fields are correct and not invalid before and during a operation of reading or writing for a channel.

A denial of service attack is still possible if malicious code in a process spawns a number of threads which allows it to circumvent the duplicate channel rule and create a arbitrary number of duplicate channels which depletes system resources. However to note that even in a modern Unix or Linux system this same problem can arise. This problem should be handled by user limitations instead of this explanation, and potentially the limitation for duplicates channels could be waived away as a preventative for malicious executable code - but before doing so one must realize the design methodology effect of doing so which are not implicitly stated above.