Preemptive threads, which you implemented in the previous project, provide a basis 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 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 disabled
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.
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 two fields that identify the
sender and the sending port. 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 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:
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.
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.
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.