Due Tuesday, Dec 13, 2005 (6:00 PM)
None of the projects 0..5 are required for this project, so you are free to start building on top of whichever project you like. Having implemented semaphores correctly in project 3 will make your job easier, since there are a lot of similarities between this project and semaphore implementation in project 3.
We provide two options for starting a base project 6 kernel. You can choose whichever option you find easier.
The purpose of this project is to add communication via message passing to GeekOS.
To better understand the concepts behind this project, you might want to review section 3.4.2 in the textbook first.
Message passing allows processes to communicate by sending
messages. In this project, those messages will be sent
via message queues. You can think of the message queues as
mailboxes (heretofore we'll use message queue and mailbox interchangeably).
A send to a mailbox will insert the
message to the queue of messages corresponding to that mailbox. A
receive reads from the queue and returns it to the
receiver. The queues will be FIFO so a send should append
message to the end of a queue. Correspondingly, a
receive should read from the front of a queue.
In terms of implementation, a message queue is essentially a circular buffer.
Message queues have variable size, set at queue creation time via the queue_size parameter.
Messages have arbitrary sizes, limited only by practical concerns (MESSAGE_MAX_SIZE in mqueue.h in our case).The sender uses Message_Queue_Send() for sending and the receiver uses Message_Queue_Receive for receiving; so the receiver has no idea how many bytes has the sender actually written; the FIFO mechanism will assure bytes are read in exactly the order they were received. The kernel must copy the message from the process sending the message and append it to message queue. On a receive, the kernel will read from the queue and copy the message into the buffer passed by the receiver. If the message is longer than the buffer size of the receiver, part of the message (up to the buffer size) is given to the receiver, while the rest is left in the message queue. An attempt to write to a full message queue should block the process and an attempt to read from an empty message queue will block the process (as you might have noticed, this is the UNIX semantics for pipes, but the queue size varies here). The operations of message queues are defined for the case of one process reading from a message queue and a second process writing to it. You do not need to handle the case of more than one process reading from (or writing to) the same message queue simultaneously.
Message_Queue_Destroy(int mqid) will remove the passed mailbox from the list of mailboxes the calling thread is allowed to use.
You will define a structure holding the mailbox (e.g. struct Mailbox)
in include/geekos/mqueue.h). An easy way to model the queue
is a circular buffer : an array queue_size large with
two indexes, one for reading and for writing.
The message queue API implementation should go in src/geekos/mqueue.c.
You have to add a mailbox list to the user context (user.h).
Message_Queue_Create() is a request by the current thread to use a message queue. A thread can not call Message_Queue_Send() / Message_Queue_Receive() / Message_Queue_Destroy() unless it has called Message_Queue_Create() first.The user gives a name for the mailbox, as well as the mailbox's size, and will get back a message queue ID mqid, an integer between 0 and N - 1. Your operating system should be able to handle at least 20 (thus N = 20) mailboxes whose names may be up to 25 characters long. If there are no mailboxes left (i.e., there were 20 mailboxes with unique names already given), an error must be returned.
In the implementation of your kernel function Sys_MessageQueueCreate, you will check if another thread has made this system call with the same name. If so, you must return back the mqid associated with this name. The parameter queue_size is ignored in this case. The mqid value returned will allow the calling thread to tell the kernel which mailbox it wants to use later. You also need to add this mqid to the list of mailboxes the calling thread can use, as well increment the count of registered threads which are permitted to use the mailbox. So, for each thread you have to store the list of mailbox IDs it can use, and for each mailbox, you will store the number of threads using it. (This will be used as a reference count.)
If this is the first time Message_Queue_Create() has been called by the name passed in, then find an unused mqid, and allocate message_size space associated with this mailbox. Again, add the mqid to the list of mailboxes the current thread can use, as well as incrementing the mailbox's count of authorized threads.
Whenever a thread calls Message_Queue_Send() or Message_Queue_Receive(), the kernel will check if the thread has permission to make this call. It will do so by checking if the thread has the mqid in its list of mqids that it can access If it is there, it will be allowed to execute Message_Queue_Send() or Message_Queue_Receive(). If not, the kernel should return back an error.
Message_Queue_Destroy(int mqid) will remove the passed mailbox from the list of mailboxes the calling thread is allowed to use. It will also keep track of how many threads have references to the mailbox, and delete the mailbox from the table (i.e. mark is as an unused mailbox) when the last thread that can access this mailbox calls Message_Queue_Destroy(). Note: when a thread exits, the kernel should automatically call Message_Queue_Destroy() on behalf of this thread, for all the mailboxes it has in its list.
You have to implement the semantics of the new system calls as described below.
NOTE: All user-supplied pointers (e.g. strings, buffers) must be checked for validity.
|Call||User Function||Return on success||Return on failure||Reasons for failure||Comment|
|SYS_MESSAGEQUEUE_CREATE||int Message_Queue_Create(const char *name, ulong_t queue_size)||new message queue id||< 0||
||This call should create a new message queue if it does not exist. Otherwise, it should open it in the current process.|
|SYS_MESSAGEQUEUE_DESTROY||int Message_Queue_Destroy(int mqid)||0||< 0||
||Removes this mailbox from the current thread's list of usable mailboxes. If the refcount is 0, free the mailbox.|
|SYS_MESSAGEQUEUE_SEND||int Message_Queue_Send(int mqid, void * buffer, ulong_t message_size)||0||< 0||
||Appends buffer to the message queue. Blocks if the queue is full.|
|SYS_MESSAGEQUEUE_RECEIVE||int Message_Queue_Receive(int mqid, void * buffer, ulong_t message_size)||0||< 0||
||Reads from the message queue into buffer. Blocks until the buffer can be filled.|
Please use the files in the Grading Criteria