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

Due: Wednesday, December 5, 11:59pm

In this lab, you’ll modify a web server to implement a concurrent server for managing people and the places that they have visited—something like “red pins” on a map. Part of the server’s functionality will involve acting as a client to copy pins 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 "redpin.c".

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

  $ make

  $ ./redpin port

where port is some number between 1024 and 65535. After starting redpin, 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 people: 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 people and, for each person, any number of places that they have visited. That’s equivalent to keeping track of any number of places and, for each place, any number of people who have visited the place.

Each person and each place is identified by an arbitrary string that does not include a space or newline character. A person or place identity is case-sensitive. A person and a place can each have the same name, but a place is distinct from a person with the same name.

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

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.

Finally, your server must not leak memory as long as all connections are well-behaved (i.e., any client errors are confirmed to bad query parameters). We will run your server under Valgrind to check whether it can detect any leaks.

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 an empty set of people and places. A pin operation adds person-at-place combinations to the server, and an unpin operation can remove person-at-place combinations. There is no fixed set of people and places; when a person is mentioned in a pin operation, the person is added to the set of people tracked by the server, and similarly for places. When an unpin operation removes the last pin for a person or place, then the person or place is no longer tracked by the server.

Your server must support several kinds of HTTP GET/POST requests:

In the queries described above, arguments to person, place, etc., 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, places might be supplied before people in a pin request, and the server should treat that the same as people before places.

If a query is unrecognized or missing a required argument, your server should respond with status 400 (and not crash). If a query has extra arguments that are not listed above, your server can ignore them. If a query has the same argument multiple times, your server can use any one of them; the given header-parsing code will effectively pick one for you.

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

  $ curl "http://localhost:8090/counts"

  0

  0

  $ curl "http://localhost:8090/pin?people=alice&places=warnock"

  1

  1

  $ curl "http://localhost:8090/places?person=alice"

  warnock

  $ curl "http://localhost:8090/pin?people=bob%0Acarol&places=warnock%0Amerrill"

  3

  2

  $ curl "http://localhost:8090/people"

  carol

  bob

  alice

  $ curl "http://localhost:8090/places"

  warnock

  merrill

  $ curl "http://localhost:8090/places?person=bob"

  warnock

  merrill

  $ curl "http://localhost:8090/places?person=carol"

  warnock

  merrill

  $ curl "http://localhost:8090/unpin?people=alice%0Abob&places=warnock"

  2

  2

  $ curl "http://localhost:8090/people"

  carol

  bob

  $ curl "http://localhost:8090/places?person=bob"

  merrill

  $ curl "http://localhost:8090/places?person=carol"

  warnock

  merrill

  $ curl "http://localhost:8090/copy?host=localhost&port=8090&person=carol&as=alice"

  3

  2

  $ curl "http://localhost:8090/people"

  carol

  bob

  alice

  $ curl "http://localhost:8090/places?person=alic"

  $ curl "http://localhost:8090/places?person=alice"

  warnock

  merrill

  $ curl "http://localhost:8090/places?person=dan"

  $ curl "http://localhost:8090/people?place=warnock"

  carol

  alice

  $ curl "http://localhost:8090/people?place=union"

  $

In the responses above, the order of people or places 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 pin addition, even if multiple clients are adding places for the same person list at the same time. For example, if three clients each add 1000 different places for a person concurrently, the result will be a person with 3000 places.

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 1 character 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 person’s place list, that’s also not ok.

We expect that your server exhibits good asymptotic performance. Adding N places for one person should take O(N) time, and adding N people for one place should take O(N) time. Adding N places for M people can take O(NM) time. Removing one person from one place should take O(1) time. Use the dictionary routines that we have provided to store people and places, and that should provide the right asymptotic performance. Even though we may not directly probe asymptotic performance of your server, we expect large tests to work.

We will send arbitrary people and place names through the query interface to make sure that they are is reported back intact, and we’ll try perverse people and place names 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 ones listed in Server Queries.

Support Libraries

In addition to "csapp.[ch]", the starting code in servlab-handout.zip includes "dictionary.[ch]" and "more_string.[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 dictionary_free is called or when the value is removed or 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 some tests:

Evaluation

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

Tips