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!).
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
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
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
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.
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
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 are used to identify communication endpoints. They come in
two forms: local and remote, with their own corresponding functions,
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
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:
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.
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.
If you need help with any part of the assignment, we are here to help.