Project 2: A PThread-based Network Driver

Project 2

A PThread-based Network Driver
1 General Overview A piece of code is required which will function as a (de)multiplexor for a simple network device. Calls will be made to this software component to pass packets of data onto the network. Packets arriving from the network will be demultiplexed and passed to appropriate waiting callers. The emphasis is on the concurrency, not on networking issues. The core of your solution will be one or more threads, which move packets of data between queues or buffers (amongst other things). You will be programming in C, and using the PThread libraries. PThreads enable you to dynamically create threads and provides support for both mutual exclusion locks and for condition variables (which support a simple wait/signal mechanism and allow a timeout on waits). A tutorial on Pthreads, together with sample code for a generic BoundedBuffer, is available on Canvas. If you have not already read through the Pthreads tutorial, you should do so immediately. 2 Detailed Problem You are to write a piece of code which provides the central functionality of a network device driver. The ADT you are producing will be called NetworkDriver, and you will make calls onto an instance of the NetworkDevice ADT (provided by the test harness). Calls will be made to your code from the application level, as well. Your code will be passing around pointers to PacketDescriptors, this is an ADT about which you need to know almost nothing. One of the components of the system is a PacketDescriptor constructor; this will be handed a region of memory (actually a void * pointer and a length) and it divides that into pieces each the right size to hold a PacketDescriptor. The PacketDescriptors are then passed to another component, the FreePacketDescriptorStore. The FreePacketDescriptorStore is an unbounded container, which will be used by your code and the test harness as a place from which to acquire PacketDescriptors. When they are no longer used, the PacketDescriptors must be returned to the FreePacketDescriptorStore. You are provided an existing piece of code for the FreePacketDescriptorStore, along with other components of the test harness. Similarly, you may use the BoundedBuffer described above if that is helpful within your solution. All other code must be your own work; plagiarism/collusion detection will be undertaken to check this is the case. The Makefile in the starting archive assumes that all you are providing is networkdriver.c, an implementation of the networkdriver.h interface; it also assumes the c89 standard, and uses “-W -Wall” as compiler flags. The test harness includes fake applications, which will acquire PacketDescriptors from the store, initialize their contents and then pass them to your code for delivery onto the network. The test harness includes a fake, full-duplex NetworkDevice; it can simultaneously transmit a packet onto the network and receive a packet from the network. For sending packets to the network, you can pass PacketDescriptors to the NetworkDevice for dispatch. The complication is that the NetworkDevice can only process one packet at a time, and is quite slow in doing so;
CIS 415 Project 2
-2-
therefore you may have to queue up other requests. An application thread should not normally have to wait for its packet to be placed on the network. Once it has handed it to your code, it should be allowed to return and engage in other activity. This means you are likely to need dedicated threads within your code to pass packets to the network device. Once a packet has been sent onto the network, your code should pass the descriptor back to the free packet descriptor store. The NetworkDevice will also pass packets from the network to your code. This will entail you having a PacketDescriptor ready and waiting and a thread blocked ready to handle the pseudointerrupt saying a packet has arrived. You will need to set-up a new empty packet descriptor to await the next packet and block as soon as possible waiting for it. This means that any processing of a recently arrived packet must be minimal, handing it over to another (buffered?) part of your code for dispatch by a different thread. Packets will need to be passed to the fake application layer when they are requested, and eventually the packet descriptors will be returned to the free packet descriptor store by the fake applications. Because this code is supposed to live inside the OS, you are required to use bounded sized data structures within the parts of your code that handle the passing of packet descriptors between the applications and the network device. It's possible that application threads will block, either because they are awaiting incoming packets, because the buffers for outgoing packets are full (as those data structures are supposed to be bounded), or because there are no free packet descriptors available. The thread that handles incoming packets must not block, except to await an incoming packet. So, either: the thread that processes the received packets must also not block; or, if it does and the buffer for received packets subsequently becomes full, the packet receiver thread must discard packets rather than blocking on a full buffer. In summary, you have applications that run at their own pace, and a network device that runs at a very different pace and for which the send and receive requests must be serialized. Your network driver must bridge between the two, despite the speed mismatch; in particular, it must always be ready to receive a message from the network. You are to use Pthreads and bounded data structures to provide this bridging function to implement the spec in networkdriver.h. The starting files for this exercise are available from Canvas. You should start the design of your solution now, sketching out what you are trying to achieve and the rough code needed to do it. Your sketch will most likely take the form of an interaction or collaboration diagram1. Your GTF and I will be happy to review your design after you have completed it. 3 Background information (taken from the .h files) The test harness application threads are distinguished by their PID: typedef unsigned int PID; #define MAX_PID 10 /* * A PID is used to distinguish between the different applications * It is implemented as an unsigned int, but is guaranteed not to 1 See https://en.wikipedia.org/wiki/Unified_Modeling_Language and links therein.
CIS 415 Project 2
-3-
* exceed MAX_PID. */ The network device is “full duplex” – i.e., it can write a packet and read a packet at the same time. Writing a packet entails the calling thread simply invoking a method in the device, with that thread blocking until the packet has been successfully transmitted or until an error is detected. Reading a packet entails making two calls to the device, one to register a packet descriptor for receiving the next packet, and the second to block the calling thread until a packet has been received. The network device supports the following calls – your code may invoke these: int send_packet (NetworkDevice *nd, PacketDescriptor *pd); /* * Returns 1 if successful, 0 if unsuccessful * May take a substantial time to return * If unsuccessful you can try again, but if you fail repeatedly give * up and just accept that this packet cannot be sent for some reason */
void register_receiving_packetdescriptor(NetworkDevice *nd, PacketDescriptor *pd); /* * tell the network device to use the indicated PacketDescriptor to * store the next incoming data packet; once a descriptor is used it * shouldn't be reused for a further incoming data packet as it will * contain data that is supposed to be delivered to an application; * you must therefore register a fresh PacketDescriptor before the * next packet arrives */
void await_incoming_packet(NetworkDevice *nd); /* * The calling thread blocks until the registered PacketDescriptor has * been filled with an incoming data packet. The PID field in the * incoming data packet will have been set to indicate the local * application process which is the intended recipient of the * PacketDescriptor. * * This should be called as soon as possible after the previous * call to wait for a packet returns. Of course, another PacketDescriptor * needs to have been registered before this call is reissued. * Only 1 thread may be waiting for an incoming packet. */ The fake application threads may make the following calls to your code – you must implement them. void blocking_send_packet(PacketDescriptor *pd); int nonblocking_send_packet(PacketDescriptor *pd); /* * These calls hand in a PacketDescriptor for dispatching * The nonblocking call must return promptly, indicating whether or
CIS 415 Project 2
-4-
* not the indicated packet has been accepted by your code * (it might not be if your internal buffer is full) 1=OK, O=not OK * The blocking call will usually return promptly, but there may be * a delay while it waits for space in your buffers. * Neither call should delay until the packet is actually sent!! */
void blocking_get_packet(PacketDescriptor**pd, PID); int nonblocking_get_packet(PacketDescriptor**pd, PID); /* * These represent requests for packets by the application threads * The nonblocking call must return promptly, with the result 1 if * a packet was found (and the first argument set accordingly) or * 0 if no packet was waiting. * The blocking call only returns when a packet has been received * for the indicated process, and the first arg points at it. * Both calls indicate their process identifier and should only be * given appropriate packets. You may use a small bounded buffer * to hold packets that haven't yet been collected by a process, * but you are also allowed to discard extra packets if at least one * is waiting uncollected for the same PID. i.e. applications must * collect their packets reasonably promptly, or risk packet loss. */ There are also some initialization calls, the first is for you to implement, the second is one you can use: void init_network_driver( NetworkDevice *nd, void * mem_start, unsigned long mem_length, FreePacketDescriptorStore **fpds); /* * Called before any other methods, to allow you to initialize * data structures and start any internal threads. * Arguments: * nd: the NetworkDevice that you must drive, * mem_start, mem_length: some memory for PacketDescriptors * fpds: You hand back a FreePacketDescriptorStore into * which PacketDescriptors built from the memory * described in args 2 & 3 have been put */
void init_packet_descriptor(PacketDescriptor *pd); /* * Resets the packet descriptor to be empty. * Should be used before registering a descriptor * with the NetworkDevice. */ You will need to use the FreePacketDescriptorStore facilities. You can create a FreePacketDescriptorStore with: FreePacketDescriptorStore *create_fpds(void);
CIS 415 Project 2
-5-
populate it with PacketDescriptors created from a memory range using: void create_free_packet_descriptors(FreePacketDescriptorStore *fpds, void *mem_start, unsigned long mem_length); and then acquire and release PacketDescriptors using: void blocking_get_pd(FreePacketDescriptorStore *fpds, PacketDescriptor **pd); int nonblocking_get_pd(FreePacketDescriptorStore *fpds, PacketDescriptor **pd);
void blocking_put_pd(FreePacketDescriptorStore *fpds, PacketDescriptor *pd); int nonblocking_put_pd(FreePacketDescriptorStore*fpds, PacketDescriptor*pd);
/* * As usual, the blocking versions only return when they succeed. * The nonblocking versions return 1 if they worked, 0 otherwise. * The _get_ functions set their final arg if they succeed. */ Finally, given a PacketDescriptor, you can access the embedded PID field using: PID packet_descriptor_get_pid(PacketDescriptor *pd); 4 Pseudocode for Your Driver
/* any global variables required for use by your threads and your driver routines */
/* definition[s] of function[s] required for your thread[s] */
void init_network_driver(NetworkDevice *nd, void *mem_start, unsigned long mem_length, FreePacketDescriptorStore **fpds) { /* create Free Packet Descriptor Store */ /* load FPDS with packet descriptors constructed from mem_start/mem_length */ /* create any buffers required by your thread[s] */ /* create any threads you require for your implementation */ /* return the FPDS to the code that called you */ }
void blocking_send_packet(PacketDescriptor *pd) { /* queue up packet descriptor for sending */ /* do not return until it has been successfully queued */ }
int nonblocking_send_packet(PacketDescriptor *pd) { /* if you are able to queue up packet descriptor immediately, do so and return 1 */ /* otherwise, return 0 */ }
void blocking_get_packet(PacketDescriptor **pd, PID pid) { /* wait until there is a packet for `pid’ */ /* return that packet descriptor to the calling application */
CIS 415 Project 2
-6-
}
int nonblocking_get_packet(PacketDescriptor **pd, PID pid) { /* if there is currently a waiting packet for `pid’, return that packet */ /* to the calling application and return 1 for the value of the function */ /* otherwise, return 0 for the value of the function */ } 5 Developing Your Code You must develop your code in Linux running inside the virtual machine image provided to you; all of the object files for the testharness supplied to you have been compiled in this way. This also gives you the benefit of taking snapshots of system state right before you do something potentially risky or hazardous, so that if something goes horribly awry you can easily roll back to a safe state. You should use your Bitbucket GIT repositories for keeping track of you programming work. As a reference, you can perform the command line steps below to create a new project directory and upload it to your uoregon-cis415 repository.
% cd /path/to/your/uoregon-cis415 % mkdir project2 % echo “This is a test file.” project2/testFile.txt % git add project2 % git commit –m “Initial commit of project2” % git push –u origin master Any subsequent changes or additions can be saved via the add, commit, and push commands. 6 Helping your Classmate This is an individual assignment. You should be reading the manuals, hunting for information, and learning those things that enable you to do the project. However, it is important for everyone to make progress and hopefully obtain the same level of knowledge by the project’s end. If you get stuck, seek out help to get unstuck. Sometimes just having another pair of eyes looking at your code is all you need. If you cannot obtain help from the GTF or the lecturer, it is possible that a classmate can be of assistance. In your status report on the project, you should provide the names of classmates that you have assisted, with an indication of the type of help you provided. You should also indicate the names of classmates from whom you have received help, and the nature of that assistance. Note that this is not a license to collude. We will be checking for collusion; better to turn in an incomplete solution that is your own than a copy of someone else’s work. We have very good tools for detecting collusion.
CIS 415 Project 2
-7-
7 Submission2 You will submit your solutions electronically by uploading a gzipped tar archive via Canvas. Your TGZ archive should be named “<duckid-project2.tgz”, where “<duckid” is your duckid. It should contain your “networkdriver.c” and a document named “report.pdf” or “report.txt”, describing the state of your solution, and documenting anything of which we should be aware when marking your submission. If your solution depends upon any other files that you have created, these must also be provided in the archive, along with a modified Makefile that builds your “mydemo” from the testharness files and your .o files. These files should be contained in a folder named “<duckid”. Thus, if you upload “jsventek-project2.tgz”, then we should see the following when we execute the following command: % tar –ztvf jsventek-project2.tgz -rw-rw-r-- joe/None 5125 2015-03-30 16:37 jsventek/networkdriver.c -rw-rw-r-- joe/None 629454 2015-03-30 16:30 jsventek/report.pdf Each of your source files must start with an “authorship statement”, contained in C comments, as follows: • state your name, your login, and the title of the assignment (CIS 415 Project 0) • state either “This is my own work.” or “This is my own work except that …”, as appropriate.
2 Note that if you do not structure your submission as defined in this section, your submission will not be graded, and you will receive a 0 for the project. If you do not remember how to create a submission with this structure, please review Section 6 of the handout for Project 0.
Marking Scheme for CIS 415 Project 2 Design (40) • design diagram showing dataflows and interactions in your system (16) • appropriate sizing of bounded buffers/other data structures (4) • appropriate behaviour when there is a shortage of PacketDescriptor’s for receiving packets (4) • explanation of blocking behaviour matching the requirements (8) • novel design features (8) Implementation (60) • honest statement of the state of the solution (10) • workable implementation (30) o appropriate synchronization (6) o appropriate number and initialization of threads (4) o appropriate return of PacketDescriptor’s (4) o low complexity search for next PacketDescriptor associated with the redeeming thread (6) o appropriate initialization of data structures (6) o sufficient commentary in the code (4) • working implementation (10) • excellent commentary (10)
TOTAL (100)