CS4411
Practicum in Operating Systems

Project 3: Unreliable Datagram Networking

Overview

Preemptive threads, which you implemented in the previous project, provide a basis for more sophisticated features to be added to minithreads. Your goal for this project is to add unreliable networking on top of the preemptive threads package: this makes it possible for one copy of the minithreads package to send a message to another minithreads instance running on a different computer.

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!

To achieve the goal of this project, you have to implement a "minimsg" layer on top of the raw network 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.

You will also have to construct a header that precedes the data being sent. The header packs in information that your minimsg layer uses to identify communication endpoints and must thus be standard in order for other minithreads implementations to meaningfully communicate with one another. It also has to be in an architecture-independent format so that hardware with different internal representations of integers can correctly interpret your data.

This assignment closely follows the UDP/IP analogy. The raw interface we provide is equivalent to IP. The miniport and packet send and receive operations you write are equivalent to UDP.

The interface you need to implement is in minimsg.h. We have provided you with skeletal routines to start off with. Note that you will need to closely interface with the network.h interface in order to start up the pseudo-network device and the IP-layer, to send messages and to receive them. Below, we first describe what we provide you with in terms of a network device and how you need to interact with it, (as with real networking cards, there are some elaborate constraints on when the card can be initialized), then what you need to implement in the minimsgs interface, and finally describe the miniport usage conventions you need to follow to write applications.

If written correctly, you can actually communicate with your friends' (and the TAs') instances of minithreads!

The Details

../../images/letter.gif

There are several distinct components to this project:

1. To start up the networking pseudo-device, you need to call network_initialize(). This function should be called after clock_initialize(), but before first interrupt arrives and before 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 arrive on the stack of the currently executing thread and transfers control to the "network handler" you provide, passing you a network_interrupt_arg_t pointer to dynamically-allocated the packet data. 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. It is your responsibility to free up the allocated packet data when you are done processing it.

2. You can send packets to other hosts using the network_send_packet() call innetwork.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. network_send_packet() function takes four parameters: a destination address, a pointer to a header buffer, a length field that dictates the length of the data buffer, and a pointer to the data buffer itself. The header itself is specified in miniheader.h as struct mini_header. You must use the pack_* and unpack_* to serialize these fields so that your data is in an architecture-independent format. This will ensure that your code can communicate with other machines, even those of different architectures.

Note

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, namely 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.

Minimsgs

../../images/mailbox.gif

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 blocked waiting for a packet to arrive.

Receiving messages requires decoding the packet header to determine which miniport it has been sent to, then check 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

../../images/door1.gif

Miniports are used to identify communication endpoints. They come in two forms: bound and unbound, with their own corresponding functions, miniport_create_unbound() and miniport_create_bound(). Bound ports are used for sending data and have a fixed network_address_t destination address as well as a destination miniport (which is the remote's unbound miniport). Unbound ports are used for receiving data and have fields to allow messages to be queued on it, and threads to block waiting for messages. A bound port on machine A corresponds to some unbound port at machine B that serves as the destination for a minimsg_send(). Sending from machine A also requires an unbound port at machine A to be specified. When the message arrives at machine B, a bound port will be created and returned as part of the receive, corresponding to the unbound port at machine A the message was sent from: this allows the receiver to reply. To destroy a port, bound or unbound, the miniport_destroy() function should be used. It is legal to specify a local unbound port as the destination of a send operation.

A large part of your task will involve managing the port space. To simplify this assignment, we decided not to require you to implement a nameserver. You will learn in lecture 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 ssh, mail, http, etc. do not use a portmapper 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 portmapper.

Users of your minimsg layer specify the unbound port that they wish to use for receiving messages, but this range must be within 0-32767. Bound ports are not specified by users, but are instead assigned by your minimsg layer as the need arises. These bound ports should be assigned in incremental order starting from 32768. Bound port numbers should not be reused, even if the original port was destroyed, unless you reach the end of your port-space (which is 65535).

Tips and Tricks

1. When the 'user' specified a message length larger than MINIMSG_MAX_MSG_SIZE in minimsg_send(),the request should fail.

2. When minimsg_receive() gets data longer than the size (*len) of the 'user' provided buffer, it should fill the provided buffer, discard the rest of the received message and return (*len) bytes.

3. The address in network_interrupt_arg_t may not be the same as we found in minimsg header. So you don't need to verify the match of the two addresses.

How to Get Started

../../images/door2.gif

Make a backup copy of your code from the previous project, download the code from CMS and merge.

How to Test Your Code

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.

We encourage you to test your implementation against the TAs' minithreads. During office hours, the TAs will set up one computer in the CSUG lab for this purpose. You can also test your code against your friends' implementations.

Note

A non-trivial part of your grade on this project will be how well you test your own code!

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.

Submissions

Use CMS to submit your project. You should include a README file with your name, your partner's name, and anything you think we should know. This includes documenting any broken functionality (although you will have trouble later on if you do not complete this project now, so you should not be submitting a broken project).

Final Word

Start early. If you need help with any part of the assignment, we are here to help.

Powered by Firmant