使用LRU算法，实现一个具有Cache能力的Web Proxy.
Introduction
A proxy server is a computer program that acts as an intermediary between clients making requests to access resources and the servers that satisfy those requests by serving content. A web proxy is a special type of proxy server whose clients are typically web browsers and whose servers are web servers providing web content. When a web browser uses a proxy, it contacts the proxy instead of communicating directly with the web server; the proxy forwards the client’s request to the web server, reads the server’s response, then forwards the response to the client.
Proxies are useful for many purposes. Sometimes, proxies are used in firewalls, so that browsers behind a firewall can only contact a server beyond the firewall via the proxy. A proxy may also perform translations on pages, for example, to make them viewable on web-enabled phones. Importantly, proxies are used as anonymizers: by stripping requests of all identifying information, a proxy can make the browser anonymous to web servers. Proxies can even be used to cache web objects by storing local copies of objects from servers and then responding to future requests by reading them out of its cache rather than by communicating again with a remote server.
This lab has three parts. An implementation of the first part will be submitted as your checkpoint. Your final submission will then incorporate the extensions forming the second and third parts. For the first part, you will create a proxy that accepts incoming connections, reads and parses requests, forwards requests to web servers, reads the servers’ responses, and forwards the responses to the corresponding clients. The first part will involve learning about basic HTTP operation and how to use sockets to write programs that communicate over network connections. In the second part, you will upgrade your proxy to deal with multiple concurrent connections. This will introduce you to dealing with concurrency, a crucial systems concept. In the third and last part, you will add caching to your proxy using a simple main memory cache of recently accessed web content.
You will debug and test your program with PXYDRIVE, a testing framework we provide, as well as by accessing your proxy via standard tools, including a web browser. The grading of your code will involve automated testing. Your code will also be reviewed for correctness and for style.
Logistics
This is an individual project. You are allowed only one grace day for the checkpoint and one grace day for the final.
Handout instructions
Create your GitHub Classroom repository. or by clicking the “Download handout” button on the proxylab Autolab page. Then do the following on a Shark machine:
- Clone the repository that you just created using the git clone command. Do not download and extract the zip file from GitHub.
- Type your name and Andrew ID in the header comment at the top of proxy.c.
Robust I/O package
The handout directory contains the files csapp.c and csapp.h, which comprise the CS:APP package discussed in the CS:APP3e textbook. The CS:APP package includes the robust I/O (RIO) package. When reading and writing socket data, you should use the RIO package instead of low-level I/O functions, such as read, write, or standard I/O functions, such as fread, and fwrite.
The CS:APP package also contains a collection of wrapper functions for system calls that check the return code and exit when there’s an error. You will find that the set of wrapper functions provided is a subset of those from the textbook and the lecture notes. We have disabled ones for which exiting upon error is not the correct behavior for a server program. For these, you must check the return code and devise ways to handle these errors that minimize their impact.
HTTP parsing library
The handout directory contains the file http parser.h, which defines the API for a small HTTP string parsing library. The library includes functions for extracting important data fields from HTTP response headers and storing them in a parser t struct. A brief overview of the library is given below. Please refer to the source files in your handout for the full documentation of the types, structs, and functions available for use in the library.
To create a new instance of a parser struct, call parser new(). The returned pointer can then be used as the first argument to the other functions. parser parse line() will parse a line of an HTTP request and store the result in the provided parser t struct. Parsed fields of specified types may be retrieved from the struct by calling parser retrieve() and by providing a string pointer for the function to write to. Particular headers may also be retrieved by name via parser lookup header(). Headers may instead be accessed in an iterative fashion by successive calls to parser retrieve next header().
Modularity
The skeleton file proxy.c, provided in the handout, contains a main function that does practically nothing. You should fill in that file with your proxy implementation. Modularity, though, should be an important consideration, and it is important for you to separate the individual modules of your implementation into different files. For example, your cache should be largely (or completely) decoupled from the rest of your proxy, so one good idea is to move the implementation of the cache into separate code and header files cache.c and cache.h.
Makefile
You are free to add your own source and header files for this lab. The Makefile will automatically link all .c files into the final binary. While you are free to update the provided Makefile (for example to define the DEBUG macro), the autograder will use the original Makefile to grade your solution. As such, the entire project should compile without warnings.
Other provided resources
Included with your starter code, in the pxy directory, is a pair of programs PXYDRIVE and PXYREGRESS (given as files pxydrive.py and pxyregress.py, respectively.) PXYDRIVE is a testing framework for your proxy. PXYREGRESS provides a way to run a series of standard tests on your proxy using PXYDRIVE. Both programs are documented in the PXYDRIVE user manual.
Also included, in the tests directory, is a series of 51 test files to test various aspects of your proxy. Each of these is a command file for PXYDRIVE. You will want to learn about the operation of PXYDRIVE and how each of these tests operate.
Finally, you are provided with a reference implementation of a proxy, named proxy-ref. It is compiled to execute on a Linux machine.
Part I: Implementing a sequential web proxy
The first step is implementing a basic sequential proxy that handles HTTP/1.0 GET requests. Your proxy need not handle other request types, such as POST requests, but it should respond appropriately, as described below. Your proxy also need not handle HTTPS requests (only HTTP).
When started, your proxy should listen for incoming connections on a port whose number is specified on the command line. Once a connection is established, your proxy should read the entirety of the request from the client and parse the request. It should determine whether the client has sent a valid HTTP request; if so, it should 1) establish its own connection to the appropriate web server, 2) request the object the client specified, and 3) read the server’s response and forward it to the client.
HTTP/1.0 GET requests
When an user enters a URL such as http://www.cmu.edu/hub/index.html into the address bar of a web browser, the browser will send an HTTP request to the proxy that begins with a request line such as the following:
GET http://www.cmu.edu:8080/hub/index.html HTTP/1.1\r\n
The proxy should parse the request URL into the host1 , in this case www.cmu.edu:8080, and the path2 , consisting of the / character and everything following it. That way, the proxy can determine that it should open a connection to hostname www.cmu.edu on port 8080 and send an HTTP request of its own, starting with its own request line of the following form:
GET /hub/index.html HTTP/1.0\r\n
As these examples show, all lines in an HTTP request end with a carriage return (‘\r’) followed by a newline (‘\n’). Also important is that every HTTP request must be terminated by an empty line, consisting of just the string “\r\n”.
Notice in the above example that the web browser’s request line ends with HTTP/1.1, while the proxy’s request line ends with HTTP/1.0. Modern web browsers will generate HTTP/1.1 requests, but your proxy should handle them and forward them as HTTP/1.0 requests.
Additionally, in the above example, a port number of 8080 was specified as part of the host. If no port is specified, the default HTTP port of 80 should be used.
Request headers
Request headers are very important elements of an HTTP request. Headers are key-value pairs provided line-by-line following the first request line of an HTTP request, with they key and value separated by the colon (‘:’) character. Of particular importance for this lab are the Host, User-Agent, Connection, and Proxy-Connection headers. Your proxy must perform the following operations with regard to the listed HTTP request headers:
- Always send a Host header. This header is necessary to coax sensible responses out of many web servers, especially those that use virtual hosting.
The Host header describes the host of the web server your proxy is trying to access. For example, to access http://www.cmu.edu:8080/hub/index.html, your proxy would send the following header.
It is possible that the client will attach its own Host header to its HTTP requests. If that is the case, your proxy should use the same Host header as the client. - You should always send the following User-Agent header:
User-Agent: Mozilla/5.0 (X11; Linux x86 64; rv:3.10.0) Gecko/20210731 Firefox/63.01\r\nThe header shown above on two separate lines because it does not fit as a single line, but your proxy should send the header as a single line. It is provided as a string constant in proxy.c.
The User-Agent header identifies the client (in terms of parameters such as the operating system and browser), and web servers often use the identifying information to manipulate the content they serve. Sending this particular User-Agent string may improve, in content and diversity, the material returned by some web servers. - Always send the following Connection header:
Connection: close\r\n - Always send the following Proxy-Connection header:
Proxy-Connection: close\r\n
The Connection and Proxy-Connection headers are used to specify whether a connection will be kept alive after the first request/response exchange is completed. Specifying close as the value of these headers alerts web servers that your proxy intends to close connections after the first request/response exchange.
With the exception of the Host header, your proxy should ignore the values of the request headers described above provided by the client. Instead, it should always send the headers this document specifies.
Finally, if a client sends any additional request headers as part of an HTTP request, your proxy should forward them unchanged. Forwarding other request headers is especially important when using PXYDRIVE to test your proxy, because it uses headers to coordinate the actions of its client and servers.
Port numbers
There are two significant classes of port numbers for this lab: HTTP request ports and your proxy’s listening port. The HTTP request port is an optional field in the URL of an HTTP request. That is, the URL may be of the form, http://www.cmu.edu:8080/hub/index.html, in which case your proxy should connect to the host www.cmu.edu on port 8080, and it should include the port number in the Host header (e.g., Host: www.cmu.edu:8080.)
Your proxy must properly function whether or not the port number is included in the URL. If no port is specified, the default HTTP port number of 80 should be used, which should not be included in the Host header.
The listening port is the port on which your proxy should listen for incoming connections. Your proxy should accept a command line argument specifying the listening port number for your proxy. For example, with the following command, your proxy should listen for connections on port 12345:
linux> ./proxy 12345
The proxy must be given a port number every time it runs. When using PXYDRIVE, this will be done automatically, but when you run your proxy on its own, you must provide a port number. You may select any non-privileged port (greater than 1,024 and less than 32,768) as long as it is not used by other processes. Since each proxy must use a unique listening port, and many students may be working simultaneously on each machine, the script port-for-user.pl is provided to help you pick your own personal port number.
Use it to generate a port number based on your Andrew ID:
linux> ./port-for-user.pl
bovik bovik: 5232
The port, p, returned by port-for-user.pl is always an even number. So if you need an additional port number, say for the Tiny server, you can safely use ports p and p + 1.
Error handling
In the case of invalid requests, or valid requests that your proxy is unable to handle, it should try to send the appropriate HTTP status code back to the client (see clienterror() in tiny.c). Read more about HTTP status codes at: https://developer.mozilla.org/en-US/docs/Web/HTTP/Status
In particular, your proxy must be able to respond to a POST request with the 501 Not Implemented status code. The request line for a POST request will resemble the following.
In other cases, it is acceptable for your proxy to simply close the connection to the client when an error occurs, using close(). Note that in all error cases, you should always clean up all resources being used to handle a given request, including file descriptors and allocated memory.
Note: Upon normal execution, your proxy should not print anything. However, you should consider having a verbose mode (set with -v on the command line) that prints useful information for debugging. Completing Part I satisfies the requirements for the project checkpoint. See Section 7 regarding how your proxy will be evaluated for the checkpoint.
Part II: Dealing with multiple concurrent requests
Production web proxies usually do not process requests sequentially; they process multiple requests in parallel. This is particularly important when handling a single request can involve a lengthy delay (as it might when contacting a remote web server). While your proxy waits for a response from the remote web server, it can work on a pending request from another client. Indeed, most web browsers reduce latency by issuing concurrent requests for the multiple URLs embedded in a single web page requested by a single client. Once you have a working sequential proxy, you should alter it to simultaneously handle multiple requests.
POSIX Threads
You will use the POSIX Threads (Pthreads) library to spawn threads that will execute in parallel to serve multiple simultaneous requests. A simple way to serve concurrent requests is to spawn a new thread to process each request. In this architecture, the main server thread simply accepts connections and spawns off independent worker threads that deal with each request to completion and terminate when they are done. Other designs are also viable: you might alternatively decide to have your proxy create a pool of worker threads from the start. You may use any architecture you wish as long as your proxy exhibits true concurrency, but spawning a new worker thread for each request is the most straightforward approach.
A new thread is spawned in Pthreads by calling pthread create with a start routine as its argument. New threads are by default joinable, which means that another thread must clean up spare resources after the thread exits, similar to how an exited process must be reaped by a call to wait. For a server, a better approach is to detach each new thread, so that spare resources are automatically reaped upon thread exit. To properly detach threads, the first line of the start routine should be as follows:1
pthread_detach(pthread_self());
Race conditions
While multithreading will almost certainly improve the performance of your web proxy, concurrency comes at a price: the threat of race conditions. Race conditions most often arise when there is a shared resource between multiple threads. You must find ways to avoid race conditions in your concurrent proxy. That will likely involve both minimizing shared resources and synchronizing access to shared resources. Synchronization involves the use of locks, which come in many varieties. The Pthreads library implements the locking primitives you will need, as is discussed in Section 6.2.
Thread safety
The open clientfd and open listenfd functions described in the CS:APP3e textbook (and included in csapp.c) are based on the modern and protocol-independent getaddrinfo function, and thus are thread safe.
Part III: Caching web objects
For the final part of the lab, you will add a cache to your proxy that keeps recently used Web objects in memory. Note that a software cache bears little relation to a hardware cache, such as the one you simulated in the Cache Lab assignment. Instead, it functions as a key-value storage, saving some block of data with an associated key, such that future requests of the key will return the stored data. Typically, a software cache is implemented using standard data structures, such as linked lists, arrays, and dynamically allocated memory blocks.
The HTTP standard defines a complex model by which web servers can give instructions as to how the objects they serve should be cached and clients can specify how caches should be used on their behalf. However, your proxy will follow a much simpler approach. When your proxy receives a GET request from a client, it should treat the URL as a key. When it then receives the requested web object from the server, it should store the object in its cache with this key. Whenever another GET request arrives with the same URL, it can retrieve the contents from its cache and respond to the client directly, rather than making a new request to the server.
Since your cache serves only to boost the performance of the proxy, it need not store every object that has ever been requested. Instead, it should limit the amount of memory used by bounding the size of the maximum cached object, as well as the total memory used for the cache.
The following two parameters (given as constants in proxy.c) define the two constraints on your cache size:1
2
The maximum object size of 100 KiB limits the maximum size of a web object that can be stored in the cache, where a “web object” consists of the complete response made by a server to a client, including any response headers. The maximum cache size of 1 MiB limits the sum of the sizes of all web objects stored in the cache. Neither the URL keys nor the data structures you use to implement the cache are included in either of these limits.
It is mandatory for you to dynamically allocate just enough space for your web objects and your keys, and that you do not assume any fixed upper bound on the number of web objects that will be stored in the cache. Allocate only the space your cache requires, and make sure you do not have any memory leaksa server program will fail if it cannot maintain a tight bound on the total storage it requires.
One way to implement a correct cache is to declare a local array of size MAX OBJECT SIZE in the function that handles a new connection. The function can then accumulate data as it is received from the server. If the entirety of the web server’s response is read before the maximum object size is exceeded, then space for a block can be allocated (via malloc), the contents copied into the block via memcpy, and a pointer to the block can be stored as cache data.
Eviction policy
Your proxy’s cache should employ a least-recently-used (LRU) eviction policy. (It need not be strictly LRU, since requests are processed concurrently, but it should be something reasonably close.) The initial creation of an object, as well as any reuse of the object count as uses. Since web objects vary in size, it may be necessary to evict multiple smaller objects to make room for a larger one.
Synchronization
Accesses to the cache must be thread safe; ensuring that cache access is free of race conditions. This requirement will likely be a challenging aspect of the lab. In general, you will get maximum performance by having the threads hold a lock for the cache for as short a time as possible.
It is acceptable to have a single, mutual exclusion lock to control access to the cache, both for scanning the cache for a matching key and for inserting an element into the cache. However, we require that a thread must release this lock before it writes a cached web object to the client socket. Otherwise, a slow, faulty, or malicious client could cause the proxy to hang up for an indefinite amount of time while the cached object is being transmitted to it.
The requirement that a thread must release its lock on the cache before transmitting an object to the client creates a potential race conditionif other requests cause the object to be evicted, another thread may attempt to free the storage while the object is still being transmitted. The best approach is to use reference counting, where there is an integer count associated with each object. The reference count for an object should be incremented when it is stored in the cache and decremented when it is removed. When a thread retrieves an object from the cache it increments the reference count and decrements it when it is done transmitting the object to a client. When the reference count drops to 0, the object can safely be freed. Be sure to protect all operations on a reference count with a mutual exclusion lock, or else these operations can cause synchronization errors. (Reference counting is described in the context of file descriptors in Section 10.6 of the textbook.)
Although the book describes the use of semaphores for mutual exclusion, we do not allow you to use them. Instead, you should use a mutual exclusion lock, defined in Pthreads as data type pthread_mutex_t, and supporting operations pthread_mutex_lock and pthread_mutex_unlock.
Evaluation
The grading standards for the assignment are shown in Figures 1 and 2. Grading will be via a combination of automatic testing and a manual review of your code. The automatic grading will be done by running PXYREGRESS with the same command files you are provided. There are a total of 51 files, divided into four series, labeled A-D, as described in Section 7 of the user manual.
As shown in Figure 1, your checkpoint grade will be determined solely by the results of the tests in series A and B. These can be passed by a serial proxy. There will be no style grading or manual inspection of the checkpoint code.
As shown in Figure 2, your final submission will be evaluated using all four series. Series C tests can only be passed by a proxy that supports concurrent requests. Series D can only be passed by a proxy that supports caching. The first five of these can be passed by a serial proxy (with caching). The remaining ones require a concurrent proxy.
You must pass all of the A/B tests in order to obtain any points in the C/D tests.
Finally, there are a total of 4 style points, also described below.
Autograding with PXYREGRESS
The PXYDRIVE testing framework is included in the handout in the subdirectories pxy (code) and tests (command files).
A typical invocation of PXYDRIVE from your code directory would be:
linux> pxy/pxydrive.py -p ./proxy -f tests/A01-single-fetch.cmd
With this invocation, the proxy will operate internally, under the control of PXYDRIVE. Alternatively, the proxy can be set up and run externally:
linux> ./proxy 15213 &
linux> pxy/pxydrive.py -P localhost:15213 -f tests/A01-single-fetch.cmd
(Normally, these two lines would be executed in separate terminal windows.) Running the proxy externally makes it possible to use programs such as GDB and VALGRIND to help with debugging. See Section 7 of the user manual for more detailed instructions.
The checkpoint runs the tests in the A and B series. You can perform this test with the command:
linux> pxy/pxyregress.py -p ./proxy -s AB
The final testing will be done with a more comprehensive set of concurrency checks, inserting random delays to exercise possible races, checking for thread-unsafe functions, checking that no write to a socket occurs while a thread is holding a lock, and checking for semaphores. You can perform this test with the command
linux> pxy/pxyregress.py -p ./proxy -c 4
For your convenience, the driver Autolab will use to test your submission is included as the file driver.sh. For testing the checkpoint submission, it can be invoked as:
linux> ./driver.sh check
For testing the final submission, it can be invoked as:
linux> ./driver.sh
Style Grading
The style points include a combination of points for code correctness and for coding style. Your TAs will examine your code for any correctness issues that weren’t detected by the earlier tests. In particular, we will be looking for errors such as race conditions, thread safety issues, non-LRU cache implementations, improper error handling, and memory and file descriptor leaks.
Style points will be awarded based on the usual criteria. Proper error handling is as important as ever, and modularity is of particular importance for this lab, as there will be a significant amount of code. You should also strive for portability.
Real-World Testing
Along with PXYDRIVE, you can also test your proxy’s operation using real web browsers and servers. You must set up and run these tests using standard tools, including those described here.
Tiny web server
Your handout directory includes the source code for the CS:APP Tiny web server. While not a fullfunctioning server, the server supports the operations required for this assignment. You can modify the code as you see fit.
The tiny server is a good reference for your proxy implementation because it deals with HTTP requests. Keep in mind, however, that it is not a proxy, and so its features do not exactly match those you will need in your program. Remember especially that your proxy doesn’t serve its own content; it simply relays content from the server to the client.
curl
You can use curl to generate HTTP requests to any server, including your own proxy. It is an extremely useful debugging tool. For example, if your proxy and Tiny are both running on the local machine, Tiny is listening on port 15213, and proxy is listening on port 15214, then you can request a page from Tiny via your proxy using the following curl command:
linux> curl -v --proxy http://localhost:15214 http://localhost:15213/home.html
Web browsers
Eventually you should test your proxy using the most recent version of Mozilla Firefox. Visiting selection About Firefox in the Firefox menu will automatically update your browser to the most recent version.
To configure Firefox to work with a proxy, visit Preferences]Network Proxy]Settings in the Firefox menu and set the manual proxy configuration with your host name of the specific Shark machine you are using and with the port number for your proxy.
It will be very exciting to see your proxy working through a real Web browser. Although the functionality of your proxy will be limited, you will notice that you are able to browse many websites through your proxy.
An important caveat is that you must be very careful when testing caching using a Web browser. All modern Web browsers have caches of their own, which you should disable before attempting to test your proxy’s cache.
Handin instructions
The provided Makefile includes functionality to build your final handin file. Issue the following command from your working directory:
linux> make handin
The output is the file ../proxylab-handin.tar. Simply upload it to Autolab. Autolab will use your Makefile to rebuild your proxy from scratch, and it will then run tests using PXYREGRESS.
Resources
- Chapters 10-12 of the textbook contains useful information on system-level I/O, network programming, HTTP protocols, and concurrent programming.
- RFC 1945 (https://tools.ietf.org/html/rfc1945) is the complete specification for the HTTP/1.0 protocol. The specification is large and complex. You only need to implement the portions of the protocol we describe in this document.
- HTTP/1.0 has been obsolete since the early 2000s. For modern-day HTTP specifications, see https://developer.mozilla.org/en-US/docs/Web/HTTP/Resources_and_specifications. However, implementing HTTP/1.1 would require our proxy to implement Connection: keep-alive, which would add additional complexity.
Advice
- It is important to adopt the proper mindset when writing a server program. Think carefully about how long-running processes should react to different types of errors, including network failures and malformed data. Your server should do its best to continue in the face of errors. For example, it’s OK to fail to respond to a malformed request from a client, but this should not cause your program to terminate. Robustness implies a higher level of code quality, as well, avoiding defects such as segmentation faults, memory leaks, and file descriptor leaks.
- Your proxy will have to do something about SIGPIPE signals. The kernel will sometimes deliver a SIGPIPE to a process when a socket gets disconnected. Although the default action for a process that receives SIGPIPE is to terminate, your proxy should not terminate due to that signal. (To generate the SIGPIPE signal in Firefox, press F5 twice in quick succession to reload the page.)
- Sometimes, calling read to receive bytes from a socket that has been prematurely closed will cause read to return -1 with errno set to ECONNRESET. The same result can occur when calling write to send bytes on a socket that has been prematurely closed. Your proxy should not terminate due to these errors.
- Remember that not all content on the web is ASCII text. Much of the content on the web is binary data, such as images and video. Ensure that you account for binary data when selecting and using functions for network I/O. In particular, you should never use string functions (e.g., strlen and strcpy) on web data, since these will terminate prematurely when then encounter a byte with value 0, which can occur at any position in a binary file. (The preferred way to copy data is to use memcpy.)
- You can assume that the request and header lines will be ASCII text, and you can assume that there is some reasonable upper bound on their line lengths.
- Similarly, it is inefficient to use line-oriented I/O routines, such as rio readlineb, on binary data. These routines will break the data into chunks according to the placement of newline characters (hex value 0x0A). With binary data, these can appear in arbitrary positions in a file. Instead, use functions, such rio readn and rio readnb, that operate independently of the data values.
- Forward all requests as HTTP/1.0 even if the original request was HTTP/1.1.
- Firefox (like all modern web browsers) has useful debugging tools you may take advantage of. The network tab allows you to view the status of network requests, which is useful for determining if your threads terminate and if all requests are fulfilled.
- There are several ways you can track the LRU state of the cached objects. One way is to keep a counter that is incremented for each request, storing the value of the counter each time a cached object is accessed. Another way is to store the cache as a list and move an object to the head of the list each time it is referenced. It’s up to you to select an implementation. Just make sure to use synchronization primitives to avoid race conditions on the counters, the lists, and other shared data structures.
- Avoid an overly complex design. If your synchronization code is too complex for you to easily comprehend, it almost certainly has bugs! Your first version should be the simplest one that satisfies the functional requirements. Then you can refine it to improve efficiency. A correct, but slow program is far preferable to a fast, buggy one.