Project 3
From CS415
| Table of contents |
Overview
Preemptive threads, which you implemented in the previous project, provide 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.
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 (see the extra credit section, or wait until the next assignment!).
The Details
The interface you need to implement is in minimsg.h. We have provided you with skelatal 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 implement to facilitate uniform applications.
To start up the networking pseudo-device, you need to call network_initialize(). This function should be called after clock_initialize(), 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. 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 casted 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_addres_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
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 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
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 datastructures 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:
- Use port numbers 0, 1, 2, for successively-created local miniports. Do not reuse port numbers, even if the original port using a number is destroyed, unless you reach the end of your port-space (which should be about 65535 ports).
- Ignore intervening calls to create remote ports. This includes remote ports automatically created by a receive operation. The sequence of port creation operations "local, remote, local, remote, local, local" should number the local ports 0, 1, 2, 3.
The reason for these rules is to make it as easy as possible for a machine A to predict what port numbers another machine B will be using for its ports: in order to send to a miniport at B, A has to know its number. To implement these conventions, we suggest you start numbering local ports at 0, and remote ports at 32768.
Extra Information: Function minimsg_receive has to create a miniport for every message received and the application is responsible for distroying 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 distroyed 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 surogate for a local port (just a "pointer" to the real port) that can be safely distroyed by the aplication without affecting the local miniport. You should handle this special "pointer" local ports internally.
Other tips:
- network_initialize prints the ip address of the machine the code is running on so that you can contact this machine from another one.
How to Get Started
- Backup your old code.
- Download the project 3 code.
- Add the new .h and .c files to your project.
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.
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.
For the Adventurous
Note: These suggestions for an extra challenge will be examined but not graded. They will have no impact on the class grades. They are here to provide some direction to those who finish their assignments early and are looking for a way to impress friends and family.
Add reliable message delivery to minimessages. Each packet sent should be resent until the receiver acknowledges its receipt, or until timeout. Each receive should block until either a packet arrives or a receive timeout value is exceeded. You do not need to have more than one packet outstanding on any one connection.
Final Word
Here are the frequently asked questions about Project 3.
