CSAPP - Proxylab

挂梯子每个人都玩过，但你知道梯子的原理吗。最后一个lab，实现一个HTTP代理服务器。本实验难度相对前面两个lab有所下降，但综合性比较强，涉及教材最后三章的所有内容以及malloc和cache两个lab。

项目结构

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


.
|-- csapp.c /*  
|-- csapp.h  *  这三个文件是项目主体，可以随意修改
|-- proxy.c  */
|-- driver.sh         # 测评脚本
|-- free-port.sh     /*
|-- nop-server.py     * 工具脚本
|-- port-for-user.pl  */
`-- tiny
    |-- cgi-bin/ # 动态程序
    |-- static/  # 静态文件
    |-- csapp.c /*
    |-- csapp.h  * 课本中提到的tiny实现，建议详细阅读
    `-- tiny.c   */ 

csapp.c

csapp.c和csapp.h是课本后三章提到的函数代码实例，包括以下几组函数实现：

进程控制：Fork(),Execve(),Wait(),Kill(),Sleep(),Pause()…
信号控制：Signal(),Sigprocmask(),Sig***set()
I/O操作：Open(),Read(),Write(),Lseek(),Close()…
- Signal-safe I/O
- Standard I/O
- Robust I/O
- 目录操作：Opendir(),Readdir(),Closedir()
动态内存分配：Malloc(),Realloc(),Calloc(),Free()
- 内存映射：Mmap(),Nunmap()
Socket接口：Socket(),Bind(),Listen(),Accept(),Connect()
- 网络信息：Getaddrinfo(),Gethostbyname(),Inet_ntop()…
- 可重入接口：Open_clientfd(),Open_listenfd()
Pthreads多线程：create(),join(),cancel(),detach(),exit(),self(),once()
POSIX信号量：Sem_init(),P(),V()

这也太多了8。实际上这些都是系统函数的封装，我们并不需要用到所有函数。可以看到，本实验将后三章讲述的内容全部抛出，让我们自己思考并选用这些工具来完成目标。当然，也可以随意修改这些封装或者直接使用系统接口。

tiny.c

此外，tiny目录下也有相同的csapp.c和csapp.h，而tiny.c是课本上提到的简易web服务器实现，于是我们可以将其作为proxy的初始代码框架。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


int main(int argc, char **argv){
  int listenfd, connfd;
  char hostname[MAXLINE], port[MAXLINE];
  socklen_t clientlen;
  struct sockaddr_storage clientaddr;
  listenfd = Open_listenfd(argv[1]);
  while (1) {
    clientlen = sizeof(clientaddr);
    connfd = Accept(listenfd, (SA *)&clientaddr, &clientlen);
    Getnameinfo((SA *) &clientaddr, clientlen, hostname, MAXLINE, port, MAXLINE, 0);
    printf("Accepted from (%s, %s)\n", hostname, port);
    doit(connfd);
    Close(connfd);
  }
}

Socket接口是一切网络程序的底层，有关socket模型请随便搜索那一张流程图并熟记于心（或者参考👴的文章）。这里简单总结一下要点：

地址标记主机，端口标记进程。

客户端执行Connect()，服务器执行Bind(),Listen(),Accept()。

unix系统中一切皆文件，打开的文件通过文件描述符fd标记。

网络连接也是一种特殊的文件，即Socket()也返回一个fd。

于是对该fd使用传统I/O函数即可进行通信内容的读写。本质上就是读写Socket提供的缓冲区

于是服务器需要维护listenfd,connfd两个fd分别代表监听端口和客户端端口。而服务器是一个需要长久运行的程序，因此他的核心进程往往运行着一个死循环，也称为主事件循环。在循环中服务器不断接受着客户端的请求，于是connfd在循环中不断地创建和销毁，而listenfd保持不变。而具体到单个请求的处理，tiny将其交给了doit()函数。其功能分为以下几步：

从缓冲区中读取HTTP报文
- tiny只针对GET请求做出响应
读第一行，判断HTTP方法
读取处理剩余的HTTP首部
判断请求的是静态文件还是动态程序（cgi-bin）
- 静态请求，读取文件内容
- 动态请求，调用cgi程序
此外，面对错误情况要返回相应的状态码，而服务器进程不能结束。

得分点

BasicCorrectness: 40 （基本代理）
Concurrency: 15 （并发性）
Cache: 15 （使用缓存）

Part1: Basic Proxy

proxy在client面前扮演服务器，在server面前扮演客户端。也就是说在proxy中需要同时实现这两个功能，而tiny已经有了服务器端的实现，故而只需要考虑客户端的实现即可。

1
2
3
4
5


 ┌──────┐  (2)  ┌─────┐  (1)   ┌──────┐
 │      │◄──────┤     │◄───────┤      │
 │Server│  (3)  │Proxy│  (4)   │Client│
 │      ├──────►│     ├───────►│      │
 └──────┘       └─────┘        └──────┘

具体来说，只需要修改doit函数。首先建立最简单的模型：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


// v0.1: score 16/40
void doit(int cfd){
    char request[MAXLINE], host[16],port[5], response[MAXLINE];
    /* (1) client -> proxy */
    read_req(cfd, request, host, port);
    /* (2) proxy -> server */
    int sfd = Open_clientfd(host, port);
    Rio_writen(sfd, request, strlen(request));
    /* (3) server -> proxy */
    read_res(sfd, response);
    /* (4) proxy -> client */
    Rio_writen(cfd, response, strlen(response));  
}

read_req()和read_res()封装了从Rio缓冲区读取报文的细节。下面详细介绍：

在client面前扮演server

对于请求报文，首先需要解析出地址和端口以便找到目的服务器，其次需要注意curl --proxy的第一行发包：

1

GET http://localhost:81/ HTTP/1.1

这里路径变成了服务器的完整地址，直接丢给tiny是会报404的。因此，👴直接对第一行提取host,port,path。（注意分清sscanf()和sprintf()）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


void read_req(int fd, char* message, char* host, char* port, char* path){
    rio_t rio;
    Rio_readinitb(&rio, fd);
    memset(message, 0, strlen(message));
    char buf[MAXBUF], host_port_path[MAXLINE],host_port[MAXLINE], path_line[MAXLINE];
    // Receive: "GET http://host:port/path HTTP/1.1" 
    Rio_readlineb(&rio, buf, MAXLINE);
    sscanf(buf, "GET %s HTTP/1.1\n", host_port_path);
    sscanf(host_port_path, "http://%[^/]%s", host_port, path);  
    if(sscanf(host_port, "%[^:]:%s", host, port) == 1) port = "80";
    // Send: "GET /path HTTP/1.1" 
    sprintf(path_line, "GET %s HTTP/1.1\n", path);
    strcat(message, path_line);
    while(strcmp(buf, "\r\n")) {
        Rio_readlineb(&rio, buf, MAXLINE);
        strcat(message, buf);
    }
}

在server面前扮演client

对于响应报文，则需要考虑包体长度问题。代码中设置了MAXBUF常量为8192，在测评脚本中有几个样例是远超过这个数字的。因此需要考虑流式传输，一边接受一边发送。于是doit()也需要进行修改

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


// v0.2: score 40/40
void doit(int cfd){
    char request[MAXLINE], host[16],port[5], res_buf[MAXBUF];
    /* (1) client -> proxy */
    read_req(cfd, request, host, port);
    /* (2) proxy -> server */
    int sfd = Open_clientfd(host, port);
    Rio_writen(sfd, request, strlen(request));
    /* (3) server -> proxy */
    int n;
    while ((n = Rio_readn(sfd, res_buf, sizeof res_buf)) > 0) 
        /* (4) proxy -> client */
        Rio_writen(cfd, res_buf, n * sizeof(char));
}

Part2: Concurrency

在并发性测试中，测评脚本会调用nop-server.py，其核心逻辑如下：

1
2
3
4
5


serversocket.listen(5)
while 1:
  channel, details = serversocket.accept()
  while 1:
    continue

可以看到，nop-server在接受请求之后会进入死循环，也就是说连接被永远阻塞了。这要求proxy能够同时接受多个连接。Pthread库的多线程接口较为简单，只需要将主事件循环中插入Pthread_create()，而doit()则被封装进线程的入口函数中。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


// v0.3 55/70
int main(){
  // ...
  while (1) {
    // ...
    Pthread_create(&tid, NULL, thread, connfd);
  }
}
void thread(int fd){
  Pthread_detach(pthread_self()); // 设置为可分离状态，自动回收资源
  doit(fd);
  Close(fd);
}

Part3: Cache

在缓存测试中，测评脚本会在执行过一定的请求之后杀死tiny服务器，要求服务器对之前的请求进行保存。结合上一步的多线程，这里便存在着并发读写的问题。

而缓存的实现细节有非常多可说的部分，这里首先抽象出接口：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


// v0.4 70/70
void doit(int cfd) {
    char request[MAXLINE], host[MAXLINE],port[MAXLINE], path[MAXLINE], response[MAXLINE];
    /* (1) client -> proxy */
    read_req(cfd, request, host, port, path);
    /* (1.1) proxy -> cache */
    char *value = read_cache(&cache, &path);
    if (value != NULL) {
        /* (1.2) cache -> client */
        Rio_writen(cfd, value, strlen(value)); 
        return;
    }
    /* (2) proxy -> server */
    int n, sfd = Open_clientfd(host, port);
    Rio_writen(sfd, request, strlen(request));
    /* (3) server -> proxy */
    char buf[MAXBUF], res[MAX_CACHE_SIZE];
    while ((n = Rio_readn(sfd, buf, sizeof buf)) > 0) {
        /* (4) proxy -> client */
        Rio_writen(cfd, buf, n * sizeof(char));
        strncat(res, buf, n * sizeof(char));
    }
    /* (4.1) proxy -> cache */
    write_cache(&cache, &path, res);
    Close(sfd);
}

具体到缓存设计这里可以自由发挥。如果面向评测脚本编程，只需要缓存容量为3，连缓存删除的策略都不用实现就可以满分。不过考试就考这个LRU、OPT啥的，还是得理解一下。

下面是👴让gpt写的基于循环链表的LRU策略的缓存系统：

数据结构

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


typedef struct CacheEntry {
    char* key;
    char* value;
    struct CacheEntry* next;
    struct CacheEntry* prev;
} CacheEntry;

typedef struct {
    int size;
    int capacity;
    CacheEntry* head;
    CacheEntry* tail;
    pthread_mutex_t lock;
} Cache;

初始化

1
2
3
4
5
6
7


Cache* createCache(int capacity) {
    Cache* cache = (Cache*)malloc(sizeof(Cache));
    cache->size = 0;
    cache->capacity = capacity;
    pthread_mutex_init(&cache->lock, NULL);
    return cache;
}

读缓存

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


char* read_cache(Cache* cache, const char* key) {
    pthread_mutex_lock(&cache->lock);
    // 查找是否存在相同的 key
    CacheEntry* current = cache->head;
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            pthread_mutex_unlock(&cache->lock);
            return current->value;
        }
        current = current->next;
    }
    pthread_mutex_unlock(&cache->lock);
    return NULL;
}

写缓存

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46



void write_cache(Cache* cache, const char* key, const char* value) {
    // 初始化Entry
    CacheEntry* entry = (CacheEntry*)malloc(sizeof(CacheEntry));
    entry->key = strdup(key);
    entry->value = strdup(value);
    entry->next = NULL;
    entry->prev = NULL;

    pthread_mutex_lock(&cache->lock);

    // 查找是否已存在相同的 key
    CacheEntry* current = cache->head;
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {// 更新值
            free(current->value);
            current->value = strdup(value);
            pthread_mutex_unlock(&cache->lock);
            return;
        }
        current = current->next;
    }

    // 插入新节点到链表头部
    entry->next = cache->head;
    if (cache->head != NULL) {
        cache->head->prev = entry;
    } else {
        cache->tail = entry;
    }
    cache->head = entry;

    // 如果超过容量限制，删除尾部节点
    if (cache->size == cache->capacity) {
        CacheEntry* tail = cache->tail;
        cache->tail = tail->prev;
        cache->tail->next = NULL;
        free(tail->key);
        free(tail->value);
        free(tail);
    } else {
        cache->size++;
    }
    
    pthread_mutex_unlock(&cache->lock);
}

评价：最后一个实验满分的要求还是很低的。由于c语言编程实在繁琐，👴这个实验追求的是满分前提下的代码极简主义。

结束了吗

实际上，生产级代理服务器需要考虑的远比本实验复杂几个数量级，在此提出几个思路以抛砖引玉：

完备的协议支持：
- tiny仅支持GET方法，且不支持请求头，这实际上是被称为HTTP 0.9的一个历史版本。而目前最广泛使用的HTTP 1.1，为了实现对它的兼容，需要实现以下特性：
  - 增加HEAD、POST方法，支持头域（HTTP 1.0中被引入）
  - 支持Keep-Alive头，满足http请求重用tcp连接
  - 支持Transfer-Encoding: chunked头，实现分块传输编码，满足大文件请求的需求
  - 支持Accept-Ranges头，实现字节范围请求
  - 支持请求流水线等其他特性
- 虽然实现HTTP协议是服务器的任务，但是对代理服务器的稳健性提出了更高的要求。
- 另外，本实验实现的proxy基本上是明文http代理。然而在实际应用中https才是更常用的协议。为此代理需要实现对TLS的支持。
更高的性能
- 我们完全可以自己修改评分脚本，把对缓存的考察上点强度。为了满足更高的性能，需要更高效的数据结构，如：
  - 使用信号量代替互斥锁，使用读者写者模型
  - 使用哈希表，红黑树等高级数据结构，提高查询速度
- 从更实际的开发的角度，不必将目光局限于c语言。有大量的其他语言生态的高性能库供我们挑选。
加密传输
- 保密性也是一个重要需求。更常见的代理架构是客户端和服务器都运行着代理服务器进程，在本地代理和远程代理之间运行着私有的加密通信协议。(Shadowsocks(R), VMess/VLess, Trojan…)
路由规则
- 本地代理统管着所有出网流量，但客户端不希望所有请求都经过代理。为此需要为不同目标的流量设计不同的路由规则。
- 另一方面，客户端还希望管理多个代理服务器(clash)
- VPN和代理服务器原理不同，VPN是如何实现路由的？
猫鼠游戏
- 想象你是局域网管理员，你观察到网络中某些IP的大部分流量都集中至一个外部IP的特定高位端口，你能否判断这些IP存在异常行为？
- 你观察到某些IP的流量不再通往高位端口了，反而都是通往443端口的https流量，该外部IP运行着一个简单的网站，如何判断？
- 详情自行搜索相关论文。~~关键词：GFW~~