Server Assignment

This lab is based on the Tiny web server by Bryant and O’Hallaron for Computer Systems: A Programmer’s Perspective, Third Edition

Due: Wednesday, December 6, 11:59pm [with late penalties reduced; see announcement]

In this lab, you’ll modify a web server to implement a concurrent friend-list server. Part of the server’s functionality will involve acting as a client to introduce friends from other servers that implement the same protocol.

Getting Started

Start by unpacking servlab-handout.zip. The only file you will be modifying and handing in is "friendlist.c".

You can build and run the initial server, which is a variant of the book’s Tiny web server, with

where ‹port› is some number between 1024 and 65535. After starting friendlist, you can connect to it using a web browser or curl on the same machine with

http://localhost:‹port›/

The initial server replies to any request with a list of two friends: alice and bob. The server also prints to standard output any query parameters that it received through the request, both in the URL and as POST data.

Server Behavior

Your revised server must keep track (in memory) of any number of users and, for each user, any number of other users that are friends. The “friends” relation is symmetric: if alice is a friend of bob, then bob is a friend of alice. Each user is identified by an arbitrary string that does not include a newline character.

Any number of clients should be able to connect to the server (up to typical load limits) and communicate about any size of friend lists. The server starts with an empty set of users.

Finally, your server must be highly available as described in Availability and Client Constraints, which means that it is robust against slow or misbehaving clients. This availability requirement will require concurrency in your server implementation. For grading, we will test your server by throwing a mixture of clients—fast and slow, behaving and misbehaving—all at the same time.

Your server’s output to stdout and stderr will be ignored, so you can use those streams for logging or debugging as you see fit.

Server Queries

Your server starts out with all possible users having an empty set of friends. Equivalently: users are not added in advance, and a user is implicitly added when first mentioned in a request (either in a “user” or “friend” role for the request).

Your server must maintain the invariant that if ‹user›1 has a friend ‹user›2, then ‹user›2 has ‹user›1 as a friend.

Your server must support four kinds of HTTP GET/PUT requests that are suitable for automated clients:

• /friends?user=‹user› — Returns the friends of ‹user›, each on a separate newline-terminated line as plain text (i.e., text/plain; charset=utf-8). The result is empty if no friends have been registered for the user.

  The result can report the friends of ‹user› in any order.

• /befriend?user=‹user›&friends=‹friends› — Adds each user in ‹friends› as a friend of ‹user›, which implies adding ‹user› as a friend of each user in ‹friends›. The ‹friends› list can be a single user or multiple newline-separated user names, and ‹friends› can optionally end with a newline character.

  If ‹user› and any user in ‹friends› are already friends, then the befriend request does not create a redundant friend entry.

  The result should be a list of friends for ‹user›, the same as if the query /friends?user=‹user› were immediately sent.

  Note that a long list of friends in ‹friends› will require that the friends part of the query is sent as POST data, instead of supplied as part of the URL. The starting code already merges POST query data with URL query arguments for you, so POST is only relevant if you want to construct extra large tests.

• /unfriend?user=‹user›&friends=‹friends› — Removes each user in ‹friends› as a friend of ‹user› and vice versa. The result should be a list of remaining friends to ‹user›.

  If ‹user› and any user in ‹friends› are not currently friends, then the unfriend request ignores that user in ‹friends› (i.e., it’s not an error).

• /introduce?user=‹user›&friend=‹friend›&host=‹host›&port=‹port› — Contacts a friend-list server running on ‹host› at ‹port› to get all of the friends of ‹friend›, and adds ‹friend› plus all of ‹friend›’s friends as friends of ‹user› and vice versa.

  The given ‹host› and ‹port› should refer to some friend-list server. The server that receives the introduction request should itself not fail if the server at ‹host› and ‹port› fails to respond, and it should only import friends if the server reports success with status code 200. As long as the HTTP status code from the server at ‹host› and ‹port› is 200, then the importing server can assume that the friend list is well-formed.

  The given ‹host› and ‹port› can refer to same server that received the introduce request. In that case, as long as no other client is accessing the server at the same time, the friends for ‹friend› on the same server will be added as friends of ‹user›.

  If the ‹host› and ‹port› server is different from the one that receives the introduce request, then the ‹host› and ‹port› server’s friend registry is queried but not changed by the introduce request. Friends change only on the server that receives the introduce request.

  A user should not be registered as its own friend; if ‹host› at ‹port› includes ‹user› in the list of friends for ‹friend›, then ‹user› should not be added as a self-friend.

  A server that receives an introduce request should not return a result to the client until the introduction succeeds. The result sent back to a client that makes an import request is unspecified (but must be a valid HTTP response).

In the queries described above, ‹user›, ‹friends›, and ‹friend› should all be interpreted as UTF-8 text with the usual encoding within URLs. Basically, that means you don’t have to worry about encodings as long as you use the provided parsing functions. The order of query parameters should not matter; for example, friend might be supplied before user in a /befriend request, and the server should treat that the same as user before friend.

As an example, suppose that your server has just started running on localhost at port 8090:

In the responses above, the order of friends in a response can be different than the shown order.

Availability and Client Constraints

You must make essentially no assumptions about clients of your server. It’s ok to limit the initial request line and header lines to MAXLINE characters. Otherwise, as long as clients follow the HTTP protocol and as long as machine resources are not exhausted (including memory or allowed TCP connections), your server should continue to respond to new requests in a timely manner. Your server must not run out of resources as a result of failing to free unneeded memory or close finished connections.

You should make a good effort to report errors to clients, but it’s also ok to just drop a client that makes an invalid request. It’s ok if communication errors cause the error-checking csapp.[ch] functions to print errors; the starting server includes exit_on_error(0) so that discovered errors are printed and the function returns, instead of exiting the server process.

As long as a client is well behaved, the server should not drop a client’s addition to a friend lists, even if multiple clients are adding to the same friend list at the same time. For example, if three clients each add 1000 different friends for a user concurrently, the result will be a user with 3000 friends.

There is no a priori limit on the length of user names or time that the server must stay running. If your server runs out of memory because the given data is too large, that’s ok. If your server crashes because it didn’t expect a user name to have 0 characters or to have 1,753 characters, that’s not ok. If your server runs out of memory because it has a leak and cannot deal with thousands of sequential requests to access a user’s friend list, that’s also not ok.

We will not probe the efficiency of your server by checking whether many additions to a friend list are handled in linear time, or whether a new friend can be added in constant time. In particular, it should work to simply use the dictionary routines that we have provided to store sets of friends.

We will send arbitrary user names through the query interface to make sure that they are is reported back intact, and we’ll try perverse user names and user strings such as & or ". The "more_string.[ch]" library provides relevant encoding and decoding functions.

Your server is free to support additional queries other than the four listed in Server Queries.

Support Libraries

In addition to "csapp.[ch]", the starting code in servlab-handout.zip includes "dictionary.[ch]" and "parse.[ch]".

The "dictionary.[ch]" library provides an implementation of dictionaries with case-sensitive or case-insensitive keys. When you add to the dictionary, the given string key is copied, but the given value pointer is added as-is. When creating a dictionary, you supply a function that is used to destroy values in the dictionary when they are no longer needed. For example, if data values are allocated with malloc, supply free to be used to destroy data values when free_dictionary is called or when the value is replaced with a different one. See "dictionary.h" for more information.

The "more_string.[ch]" library provides string helpers and functions for some basic parsing and encoding functions. See "more_string.h" for details.

The starting code in servlab-handout.zip includes a few tests as sanity checks (but you’ll need more of your own):

• The "simple.rkt" script runs some basic checks and reports any issues that it detects, but it only makes single-friend requests unless you use the --multi flag, and it doesn’t use the /introduce query unless you provide the --introduce flag. If a server is running on localhost at port 8090, then

  $ racket simple.rkt localhost 8090

  or

  $ racket simple.rkt --multi localhost 8090

  or

  $ racket simple.rkt --multi --introduce localhost 8090

  reports whether problems are found for the selected functionality.

• The "trouble.rkt" script helps check how well a server responds to misbehaved clients, and it requires the server to handle concurrent connections. If a server is running on localhost at port 8090, then

  $ racket trouble.rkt localhost 8090

  reports its status. If the script doesn’t finish in 5-10 seconds, then something has gone wrong.

  The "trouble.rkt" script may cause your server to report many connection errors. That’s fine, and you may want to redirect output to /dev/null when running this test. There’s only a problem if the "trouble.rkt" script itself reports errors. If "trouble.rkt" completes after printing “Making sure that trouble is done” and if your server is still running, then that test passed.

• The "stress.rkt" script throws lots of concurrent queries at a server and uses the /introduce query. If a fresh server is running on localhost at port 8090, then

  $ racket stress.rkt localhost 8090

  runs the stress test and prints no output if no problems are found.

  The "stress.rkt" script assumes that the server state is fresh (i.e., all conversations are empty). If your server prints logging information to stdout or stderr, you’ll probably want to redirect it to /dev/null when running this test.

Evaluation

We will grade your submission based on the following functionality thresholds:

• Implementing the server enough to handle the "simple.rkt" test is worth 40 points.

• Implementing the server enough to handle the "simple.rkt" test with the --multi and --introduce flags is worth 60 points.

• Adding concurrency well enough to handle the "trouble.rkt" test is worth 80 points.

• Passing the "stress.rkt" test while limited via ulimit -v 20971520 (to disallow extreme leaks) is worth 100 points.

  In bash, you can run friendlist with the memory limit like this:

    $ (ulimit -v 20971520 ; ./friendlist 8090 > /dev/null)

Tips

• Pay attention to the ownership rules for values added to or extracted from a dictionary. See Support Libraries and the comments in "dictionary.h".

• If you use a dictionary to map keys to NULL values, then the dictionary effectively implements a set. Note that you can specify NULL instead of a value-destroying function when creating a dictionary to indicate that values do not need to be destroyed.

• Don’t try to store a set of friends as one string. If you represent a set of friends as a dictionary, and if you also map each user to a set of friends using a dictionary, then you’ll have a dictionary of dictionaries—which is a good idea.

• If you get seg faults or if values seem to be changing out from under you, don’t forget to try tools like Valgrind.

• Use functions like query_encode to ensure that an unusual user name or user string doesn’t create trouble when embedded in a URL.

• More generally, you don’t want to be in the business of encoding, decoding, or parsing strings. If you find yourself having to parse, encode, or decode a string, check again whether functions in "more_string.[ch]" could be used for the job—maybe with a slightly different approach to the communication pattern.

• You’ll need to use Pthread_create to make your server handle multiple clients concurrently, but it makes sense to add concurrency as a last step.

• When you do add concurrency, you’ll need to make sure that uses of your friends table are properly synchronized. The "stress.rkt" script mostly tries to check your server’s synchronization.