Carnegie Mellon
SCS logo
Computer Science Department
home
syllabus
staff
schedule
lecture
projects
homeworks
 
  

15-410 Project 4: Thoth-like Ports

Ports Overview

This semester we are asking you to implement inter-process communication in a style reminiscent of the IPC included in the Thoth operating system, but updated to use a port abstraction instead of process identifiers. If you're interested in operating system history, you may consult Thoth, a portable real-time operating system.

A "port" is an abstract communication device distinct from a particular task or thread. All ports live in a global namespace, each with its own unique identifier that threads may send or receive on. Within this specification, ports have the following properties:

  • Each port has one owner, which is a task.
  • Only threads within the owner task may send from that port, or receive and reply on that port.
  • Any thread may send a message to another port from a port its task owns.

Identifiers

From the perspective of the operating system, each port has a unique integer that represents it. All signed 32-bit integers are valid port ids with the exception of -1.

However, this can get somewhat ugly from a user perspective. Instead, user programs can interact with a nameserver which provides a mapping between string identifiers and numerical identifiers. We have provided you with a program called named, automatically launched by init, which implements a simple name service. A companion program, namec, allows you to query the nameserver for debugging purposes. Reading the nameserver implementation is a useful way to gain some perspective on the intended operation of the system.

Background

There are four IPC operations: port(), send(), receive(), and reply().

Typical usage is for a task to call port() to create a port. Then, one or more threads of the owning task receive on the port, waiting for messages. Another task will then send a message to the port, and wait for a reply. The send is matched with a receiving thread, and the receiving thread does some work and then replies to the message. This usage pattern is described in the code below.

It is important to note that this system has a distinction between message size and buffer size. Any time a thread provides the kernel with a buffer pointer, the buffer must be at least PORT_MSG_SIZE bytes long, so there is room for the kernel to place a maximally-sized message into the buffer. However, most messages are smaller than the maximum size, so each time a message is sent the length of the particular message is specified as a byte count; that byte count will be made available to the receiver of the message, who will thus know how many bytes in the buffer are valid. Note that, from the kernel's perspective, messages are uninterpreted byte ranges, not strings, integers, etc. Particular applications may choose to interpret message contents as they see fit.

Sample Code

The code below, available to you as soup.c and oliver.c., indicates one expected usage pattern of this IPC facility.

Single-threaded Port Client

#include <syscall.h>
#include <thread.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

#define SOUP_PORT 12 // should use nameserver instead

int main(int argc, char ** argv)
{
    char msg[PORT_MSG_SIZE];
    char plea[] = "Please, sir, I want some more.";
    int size = sizeof (plea); 
    int p;

    p = port(-1);

    strcpy(msg, plea);

    printf("Oliver: %s\n\n", msg);

    send(SOUP_PORT, p, msg, &size);

    printf("Soup Server: %s\n\n", msg);

    port(p);

    exit (0);
}

Multi-threaded Server

#include <syscall.h>
#include <thread.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

#define SOUP_PORT 12 // should use nameserver instead
#define STACK_SIZE (128*1024)
#define NUM_WORKERS 4

void *
worker(void *param)
{
    char msg[PORT_MSG_SIZE];
    char myreply[] = "What!";
    int src, size;
    int p = (int)param;
    while (1){
        receive(p, &src, msg, &size); /* ignore */
        strcpy(msg, myreply);
        reply(src, p, msg, sizeof (myreply));
    }
    return (0);
}

int main(int argc, char ** argv)
{
    int i;
    thr_init(STACK_SIZE);
    int p = port(SOUP_PORT);
    for (i = 1; i < NUM_WORKERS; ++i)
        thr_create(worker, (void *)p);
    worker((void *)p); /* does not return */
    return (0);
}

Please note that this is not the only usage pattern!

Kernel Changes

The system call interface has been expanded to include the new system calls.

The kernel will need to implement the following system calls:


int port(int request)

Create or destroy a port, depending on the following conditions:

  • If the port does not exist, create it with this task as the owner and return its identifier. If there are not enough resources to create the port, the call will fail and return -1.
  • If the port is already owned by this task, then if there are no threads in this task waiting on the port, then destroy it. Returns the port id on success, -1 on failure.
  • If the port is already owned by another process, fail and return -1.
  • If the request is -1, then the task is requesting a port with an arbitrary identifier. If there are enough resources, a port will be created and the id of the port will be returned. Otherwise, the call will fail and return -1.


int send (int dst, int src, char *msg, int *size)

Send a message from one port to another and await a reply from the destination. The message to be sent is stored in msg, and is size bytes long. If the call is successful, the reply will overwrite the sent message, the size of the reply will replace the sent message's size, and zero will be returned. If the call fails, a negative integer will be returned.

For a call to send() to be valid, the task of the sending thread must own the source port, the message buffer must be PORT_MSG_SIZE in length, the message buffer must be readable and writable, the size must be valid, and the destination port must exist. If any of these conditions are not met during the operation of send(), the call may fail.

Calls to send() are synchronous. The call will block until both a matching receive() is made from the destination port, and a matching reply() is made from the destination port.

If a send() operation specifying a particular source port has begun but not yet completed, and subsequent calls to send() are made on the same source port, the subsequent calls will be blocked until the first completes. Therefore, there will only ever be at most one outstanding send() operation per port.


int receive (int dst, int *src, char *msg, int *size)

Receive a message sent to the destination port. On success, the source port, the message, and the size of the message will be written to the locations specified, and zero will be returned. If the call fails, a negative integer will be returned.

For a call to receive() to be valid, the destination port must be owned by the caller's task, the message buffer must be PORT_MSG_SIZE in length, and the message buffer, source, and size must all be writable. If any of these conditions are not met during the duration of receive(), the call may fail.

Calls to receive() are synchronous. The thread calling receive() will block (if necessary) until a matching send() is made, at which point receive() will not be blocked. However, the sending thread will not be unblocked until a reply() is made.


int reply (int dst, int src, char *msg, int size)

Reply to a message sent from the destination port to the source port. On success, the message and size will be stored in the buffers provided by the sender, and zero will be returned. If the call fails, a negative integer will be returned.

For a call to reply() to be valid, the replying task must own the source port, the destination's outstanding send() (if any) must be to the source port, the message and size must be valid, the matching send() call must still be valid, and a receive() call matching the send() must have completed successfully. If any of these conditions are not met during the duration of reply(), the call may fail.

Calls to reply() are synchronous, but never block. If a reply completes successfully, the matching send() is unblocked. (This is the case as a reply can only be completed after receiving the message.)

Files

Copy your p3 into a directory called p4. Untar the tarball on top of the new directory, then read the README for further instructions.

Suggested Plan of Attack

  1. Review this handout together with your partner. Make sure you understand what is expected of Thoth-like ports. Review the test programs as they are released to get some helpful hints.
  2. Try to draw a state-transition diagram showing the various states a port moves through in response to operations performed on it. For inspiration you can consult the diagram for TCP. This diagram, available on logical pages 21 through 23 (physical pages 27 through 29) of RFC 793, documents a system much more complicated than Thoth IPC, and also vastly more important--it serves as the foundation for most data transmission in the Internet. If you're not used to reading state-transition diagrams, here's a hint to get you started:
    If a port is in the CLOSED state, when a "passive OPEN" call is made, TCP's action should be "create TCB" and the port should enter the LISTEN state. If a port is in the LISTEN state, when a "CLOSE" call is made, TCP's action should be "delete TCB" and the port should enter the CLOSED state.
  3. Write out detailed pseudocode for receive() and the matching pseudocode for send(). You should develop an understanding of the relationship between the two functions, the contents of port structures, the relationships between ports, tasks, and threads, and an idea of what synchronization primitives you need to use (and possibly develop.)
  4. Write out detailed pseudocode for reply() and the remaining code for send(). Write pseudocode for port().
  5. If you find yourself needing new synchronization primitives, or realizing that perhaps the ones you currently have need a bit of tweaking, take some time to get synchronization right. As long as you do so in moderation, this will likely save you time in the long run.
  6. You'll probably need to write some system-call stubs and wrappers.
  7. Write simple versions of port(), send(), and receive(). Have just enough to send a single message from a client to a server in a different task. At this point, you'll have implemented a basic form of IPC!
  8. Write out reply() and the rest of send(). At this point the nameserver and the lookup utility we provide you with should work.
  9. Round out the implementation to meet the remainder of the spec, including error handling, synchronization issues, arbitrary port ids, etc.
  10. Test like there's no tomorrow!

Some test code

The following test programs have been provided for your enjoyment.

  • soup and oliver, as described above
  • sanity checks: send_self, send_nonexist, send_else, recv_nonexist, recv_else, and port_test1
  • solidity: pingpong

Have Fun!

Make sure to have some fun with this project. You've earned it, right?

[Last modified Saturday April 26, 2008]