Assignment 6: Concurrent Web Server

                                                                                                                                                                                                                                

Due Tuesday by 11:59pm Points 100 Available Apr 8 at 1pm - Apr 24 at 11:59pm 16 days

                                               

The purpose of this assignment is to modify a web server to implement a concurrent friend-list server. Part of the server’s functionality involves acting as a client to introduce friends from other servers that implement the same protocol.

                                               

Getting started

                                               

Start by downloading and unpacking servlab-handout.zip. When you have completed the assignment, hand in only the "friendlist.c" file, which contains your solution.

                                               

To build and run the initial server, which is a variant of the textbook’s Tiny web server, type:

                                               

  make  ./friendlist 

                                               

where ‹port› is some number between 1024 and 65535. Note that only ports 2100 - 2120 are open to the outside world on the CADE machines, otherwise you will only be able to connect to it from the same subnet. 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 the section "Availability and client constraints" below, which means that it is robust against slow or misbehaving clients. This requires concurrency in your server implementation. During grading, your server will be thrown a mixture of clients—fast and slow, behaving and misbehaving—all at the same time.

                                               

Your server’s output to stdout and stderr is 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›2has ‹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› requires that the friends part of the query is sent as POST data, instead of supplied as part of the URL. The provided 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 is 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 do not 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 userin 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 no assumptions about clients of your server. It is allowed 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 is allowed to simply to drop a client that makes an invalid request. It is allowed for 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 should 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 is allowed. If your

                                               

server crashes because it did not expect a user name to have 0 characters or to have 1,753 characters, that is not allowed. 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 is not allowed.

                                               

During grading, the efficiency of your server will not be probed 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.

                                               

During grading, arbitrary user names will be sent through the query interface to make sure that they are reported back intact, and perverse user names and user strings such as &or " will be tried. The more_string.[c/h] library provides relevant encoding and decoding functions.

                                               

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

                                               

Support libraries

                                               

In addition to csapp.[c/h], the provided code includes dictionary.[c/h] and parse.[c/h].

                                               

The dictionary.[c/h] 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.[c/h] library provides string helpers and functions for some basic parsing and encoding functions. See more_string.h for details.

                                               

The provided code includes several tests:

                                               

• The simple.rkt script runs some basic checks and reports any issues that it detects. It makes single-friend requests unless you use the --multi flag. It does not 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

                                               

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 does not finish in 5-10 seconds, then something has gone wrong.

                                                                 

  The trouble.rkt script may cause your server to report many connection errors. That is expected, and you may want to redirect output to /dev/null when running this test. There is only a problem with our server only 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 many 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. The stress test outputs what it is currently doing (e.g. "friending", "unfriending", "introducing", "checking friends"). It should not print any other output if it passes.

                                                                 

  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 should redirect it to /dev/null when running this test.

                                                                 

  Evaluation

                                                                 

  Your submission will be graded based on the following functionality thresholds:

                                                          
•                                                 

                                                                                                                                                                                                                                

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

                                                                                                                                                                                 

                                                                                                                                                

• Your server must not have any memory leaks.

                                                                                                                                                                                               

•                                                         
•                                                                 

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

                                                          
•                                                        
•                                                                 

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

                                                          
•                                                        
•                                                                 

  Passing the previous tests and adding concurrency well enough to handle the trouble.rkt test is worth 80 points.

                                                          
•                                                        
•                                                                 

  Passing the previous tests and passing the stress.rkt test while limited via ulimit -v 20971520 (see below) is worth 100 points.

                                                                 

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

                                                                 

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

                                                                 

  Tips

                                                          
•                                                 

                                               

1.                                                         
2.                                                                 

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

                                                           
3.                                                        
4.                                                                 

   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.

                                                           
5.                                                        
6.                                                                 

   Do not 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 have a dictionary of dictionaries—which is a good idea.

                                                           
7.                                                        
8.                                                                 

   If you get segmentation faults or if values seem to be changing out from under you, use a tool like Valgrind to help find and fix your mistake.

                                                           
9.                                                        
10.                                                                 

    Use functions like query_encode to ensure that an unusual user name or user string does not create trouble when embedded in a URL.

                                                            
11.                                                        
12.                                                                 

    More generally, you do not 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.[c/h] could be used for the job—maybe with a slightly different approach to the communication pattern.

                                                            
13.                                                        
14.                                                                 

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

                                                            
15.                                                 

                                                                                                                                               

                                                                                                                                                

8. When you do add concurrency, you must make sure that uses of your friends table are properly synchronized. The stress.rkt script mostly checks your server’s synchronization.