Preemption, which you implemented in the previous project, provides a basis for more sophisticated features to be added to minithreads. Your goal in this project is to add unreliable networking on top of the preemptive threads package: it should be possible for one copy of the minithreads package to send a message to another minithreads instance running on a different computer, and even for different threads in the same package to exchange messages.
We have provided you with a simple "raw" interface to the network, which behaves like IP: it allows a thread running in a minithreads package on machine A to send a packet to the minithreads package running on machine B. When the packet arrives, it raises a network interrupt. This interface is not very convenient for application programming, since it does not allow the sender to control which thread at machine B will receive the message!
The goal of this project is to add a "minimsg" layer on top of the raw interface, which implements "miniports". Each instance of the minithreads system maintains a collection of local miniports. Miniports serve as destination and source identifiers, uniquely identifying the connection (and the set of threads) to which the packet needs to be delivered. Senders name not only the destination machine, say B, but also the port number, say X, to which their packet should be delivered. When the packet arrives at B, it is queued at the appropriate miniport, waiting to be received.
This assignment closely follows the IP/UDP analogy. The raw interface we provide is equivalent to IP. The miniport and packet send and receive operations you write are equivalent to UDP. To make the project tractable, we omit a few details, such as UDP checksums and fragmentation of long datagrams (for that you'll have to wait until the next assignment!).
To start up the networking pseudo-device, you need to call
network_initialize(). This function should be called after
minithread_clock_init(), but before interrupts are enabled
and thread scheduling starts because the network interrupt
initialization shares code with the clock interrupt
mechanism. Network_initialize takes a "network handler" as an
argument. Analogous to the clock_handler from the previous assignment,
you will get an interrupt every time a packet arrives. This interrupt
will be taken on the stack of the currently executing thread, thereby
interrupting it. Once minithreads figures out that the cause of the
interrupt was a network packet, it will invoke the "network handler"
you provide. At that point, you can do anything you like to process
the packet, but note that you are executing in interrupt mode and
should try to finish as soon as possible and resume execution.
You can send packets to other hosts using the
network_send_packet() call in network.h. The remote host
that the packet is destined for is identified by the
network_address_t type. Packets are passed by two
arguments, a char* buffer, and a length field. The
maximum length of a packet that your network pseudo-device supports is
given by the MAX_NETWORK_PKT_SIZE constant in
network.h. The network_send_packet() function
takes two (buffer, length) pairs: one for the header, and one for the
data; the buffers get concatenated before they're sent, and it's the
receiver's job to strip the header off the packet when it
arrives.
Extra Information: The parameter to
your network_handler should be cast into a pointer to a
network_interrupt_arg_t. The information about the packet received is
stored into the fields of network_interrupt_arg_t: addr
is the network_address_t of the sender, buffer is an
array containing the message (the header followed by the data) and
size is the size of the message (header size plus data
size). You have to unpack the header and the data and for this you
have to remember the size of the header.
Your minimsg layer needs to send and receive packets on a best-effort basis. This means that, on the sender's side, you need to assemble a header that identifies to whom the packet is directed, and on the receiver's side, you need to examine the header, figure out the destination, enqueue the packet in the right place and wake up any threads that may be sleeping, waiting for a packet to arrive.
minimsg_send() is only required to assemble a header for
the message that will be sufficient on the receiving end to identify
the recipient. Since the recipient will probably want to respond to
this packet, you will need to include fields that together with the
information received in the handler's parameter identifies the
sender. You do not need to implement UDP-fragmentation, a time-to-live
field, or a checksum for this assignment.
Receiving messages requires decoding the packet header to determine which miniport it has been sent to, then checking if a thread is blocked waiting to receive a message from that miniport. If so, that thread can be woken up, otherwise, the message must be queued at the miniport until a receive is performed. If multiple threads are waiting to receive a packet, only one should be woken up, and incoming packets should be routed to the waiting threads in round-robin fashion. That is, if threads A, B and C are waiting to receive on port X, A should get packet 1, B packet 2, C packet 3. There should be just one copy of each packet, and no thread should receive less than one packet.
Though best-effort delivery is fine for this project, your code should
not introduce "more unreliable" operation! For instance, if a thread
on machine A sends a stream of messages to a single
port on machine B, which arrive in the order M1, M2, ...,
then that's the order they need to be returned by receive operations on
that port, with no additional duplication or packet loss.
Miniports are used to identify communication endpoints. They come in
two forms: local and remote, with their own corresponding functions,
miniport_local_create() and
miniport_remote_create(). Remote ports are data
structures that host A uses to identify ports on host B. Local ports
identify other ports on host A itself. A remote port has a
network_address_t to specify the remote machine, and a
miniport identifier to distinguish miniports on that machine. A local
port has some additional fields to allow messages to be queued on it,
and threads to block waiting for messages. A remote port on machine A
corresponds to some local port on machine B, and serves as the
destination for a minimsg_send(). Sending from machine A
also requires a local port at machine A to be specified. When the
message arrives at machine B, a remote port will be created and
returned as part of the receive, corresponding to the local port at
machine A the message was sent from: this allows the receiver to
reply. To destroy a port, local or remote, the
miniport_destroy() function should be used. It is legal
to specify a local port as the destination of a send operation.
A large part of your task will involve managing the local port space. To simplify this assignment, we decided not to require you to implement a nameserver. Recall from the lectures that nameservers or portmappers are intended to avoid building such dependencies into programs. Therefore, in order to identify applications residing on remote hosts, programs will have to reference hard-coded port numbers. This isn't too unrealistic - today, many popular services, such as remote login, mail, time, etc. do not use a nameserver but instead reside at well-known TCP or UDP ports. Other programs then use these magic numbers to connect to these services on remote machines without going through a nameserver.
Each new local miniport should get a unique number. To make it easy to test your code, please follow these two conventions:
Extra Information: Function minimsg_receive has to create a miniport for every message received and the application is responsible for destroying this miniport when is no longer needed. If the message is received from a local port, the same local port cannot be returned since it will be destroyed and also a copy of the local port will complicate the internal bookkeeping since now multiple local miniports can have the same port number. For this reason you should create a special type of miniport that is just a surrogate for a local port (just a "pointer" to the real port) that can be safely destroyed by the application without affecting the local miniport. You should handle this special "pointer" local ports internally.
It's crucial that systems code be correct and robust. You must test your code with reasonable and unreasonable test cases, and ensure that it behaves correctly.
To facilitate testing of minimessages, we provided you with some test
programs. It's a good idea to start with these, and develop your own
tests as you need them. The tests appear in
network[1-6].c, and they are example uses of the minimsg
interface. Besides network tests, there are other programs used to
test the alarm and preemption implementation.
Do not forget to check for memory leaks. Your threads package should not run out of memory when large numbers of ports are created and destroyed.
Now that we have local and remote message ports on our minithreads system, we have opened up a wealth of application possibilities. Rohan, one of the TA's, has written a simple streaming audio app that we will provide you. You can use it to test the efficiency of your implementation. We will run a race at the end to see which group has the best performance, with the winner receiving CS414/415 glory.
Build a nameserver that sits on a given miniport and implements the following protocol:
If you need help with any part of the assignment, we are here to help.