On this page:
Getting Started
Server Behavior
Server Queries
Availability and Client Constraints
Support Libraries
Evaluation
Tips

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

Not ready: This assignment may change for Fall 2018

Due: Wednesday, December 5, 11:59pm

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

  $ make

  $ ./friendlist port

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 user1 has a friend user2, then user2 has user1 as a friend.

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

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:

   $ curl "http://localhost:8090/befriend?user=me&friends=alice"

   alice

   $ curl "http://localhost:8090/befriend?user=me&friends=alice"

   alice

   $ curl "http://localhost:8090/befriend?user=me&friends=bob"

   alice

   bob

   $ curl "http://localhost:8090/friends?user=alice"

   me

   $ curl "http://localhost:8090/befriend?user=alice&friends=bob%0Acarol"

   me

   bob

   carol

   $ curl "http://localhost:8090/unfriend?user=me&friends=alice"

   bob

   $ curl "http://localhost:8090/introduce?user=me&friend=alice&host=localhost&port=8090"

   $ curl "http://localhost:8090/friends?user=me"

   bob

   carol

   alice

   $ curl "http://localhost:8090/friends?user=alice"

   bob

   carol

   me

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):

Evaluation

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

Tips