Proxy实验

本实验的所有内容均在proxy.c文件中完成。

感谢hankeke303大佬提供的思路！

Part I：实现顺序的代理服务器

实现顺序的代理服务器实际上就是一个tiny服务器的复刻。

`main`函数

main函数参考书上 P672 的实例：

现在的代理服务器只支持GET方法。如果客户端请求其他方法（如POST），我们发送给它一个错误信息，并返回到主程序，主程序随后关闭连接并等待下一个连接请求。否则，读并且忽略任何请求报头。

 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


int main(int argc, char **argv)
{
    int listenfd, connfd;
    char hostname[MAXLINE], port[MAXLINE];
    socklen_t clientlen;
    struct sockaddr_storage clientaddr;


    // 检查命令输入是否正确
    if (argc != 2) {
        fprintf(stderr, "usage: %s <port> \n", argv[0]);
        exit(1);
    }

    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 connection from (%s, %s)\n", hostname, port);
    }

    printf("%s", user_agent_hdr);
    return 0;
}

解析URL

首先在程序中定义一个URL结构体，存放一个URL的host、端口和路径。

1
2
3
4
5
6


// URL 结构体
typedef struct {
    char host[MAXLINE];
    char port[MAXLINE];
    char path[MAXLINE];
} URL;

对于一个传入的URL字符串，首先忽略掉 http:// 这种协议标识，可以通过查找//字符串来实现。

然后，我们找到第一个/字符，在这个字符后面的就是路径了。如果找不到这个字符，我们就认为访问的是根路径/。随后我们将这个字符设置为\0，方便之后端口的读取。我们通过:字符来定位端口，:后面的就是端口，如果找不到: 那么就认为端口是80，然后我们将这个字符设置为\0。

最后，剩下的字符串就是host了。

 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


void parseURL(char *s, URL *url) {
    // 忽略"http"，查找 "//" 字符串
    char *ptr = strstr(s, "//");

    if (ptr != NULL) {
        s = ptr+2;
    }

    // 找到第一个 '/' 字符，其后为路径
    ptr = strchr(s, '/');
    if (ptr != NULL) {
        strcpy(url->path, ptr);
        *ptr = '\0';    // 在原字符串中截断路径部分
    }

    // ':' 之后为端口号
    ptr = strchr(s, ':');
    if (ptr != NULL) {
        strcpy(url->port, ptr + 1);
        *ptr = '\0';
    }
    else {
        // 默认端口为80
        strcpy(url->port, "80");
    }

    strcpy(url->host, s);
}

以http://www.example.com:8080/path/to/file为例：

步骤	操作
查找`//`子字符串	指针指向`www.example.com:8080/path`
查找第一个`/`字符	`ptr`指向`/`，`s`变为`www.example.com:8080`，`url->path`得到`/path/to/file`
查找`:`字符	`ptr`指向`:`，`s`变为`www.example.com`，`url->port`得到`8080`
获取主机名	剩余部分就是主机名，复制到`url->host`，`url->host`得到`www.example.com`

函数说明：

strchr是C语言标准库<string.h>中的一个函数，用于在字符串中查找指定字符的第一次出现位置。如果找到了指定字符，返回该字符在字符串中第一次出现的位置的指针；如果没有找到指定字符，返回NULL。

strcpy是C语言标准库<string.h>中的一个函数，用于将一个字符串复制到另一个字符串中。它会复制源字符串的内容（包括字符串的结束符\0），返回目标字符串的起始地址。

`readClient`函数

readClient函数会从客户端读取请求的全部内容，并生成即将发送到服务端的新请求。

首先，从第一行读取URL扔给parseURL函数提取。

然后，设置默认的Hosts header为URL中的host。接着从接下来读取到的headers中，如果是Hosts那么就更新Hosts，如果是User-Agent、Connection和Proxy-Connection，那么就忽略（因为我们有我们要设定的专属header）。其余的header收集起来，稍后一并作为新请求发过去。

最后，向新请求字符串中写入我们生成的HTTP头和headers。

 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


void readClient(rio_t *rio, URL *url, char *data) {
    char host[MAXLINE];
    char line[MAXLINE];
    char other[MAXLINE];
    char method[MAXLINE], urlstr[MAXLINE], version[MAXLINE];
 
    Rio_readlineb(rio, line, MAXLINE);
    sscanf(line, "%s %s %s\n", method, urlstr, version);
    parseURL(urlstr, url);
 
    sprintf(host, "Host: %s\r\n", url->host);
    while (Rio_readlineb(rio, line, MAXLINE) > 0) {
        if (strcmp(line, "\r\n") == 0) {
            break;
        }
        if (strncmp(line, "Host", 4) == 0) {
            strcpy(host, line);
        }
        if (strncmp(line, "User-Agent", 10) && strncmp(line, "Connection", 10) 
            && strncmp(line, "Proxy-Connection", 16)) {
            strcat(other, line);
        }
    }
    
    sprintf(data, "%s %s HTTP/1.0\r\n"
                "%s%s"
                "Connection: close\r\n"
                "Proxy-Connection: close\r\n"
                "%s\r\n", method, url->path, host, user_agent_hdr, other);
}

`doit`函数

doit函数的功能是处理成功连接的套接字接口。

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


void doit(int connfd) {
    rio_t rio;
    char line[MAXLINE];
    Rio_readinitb(&rio, connfd);
    
    URL url;
    char data[MAXLINE];
    readClient(&rio, &url, data);

    int serverfd = open_clientfd(url.host, url.port);
    if (serverfd < 0) {
        printf("Connection failed!\n");
    }
    
    rio_readinitb(&rio, serverfd);
    Rio_writen(serverfd, data, strlen(data));
    
    int len;
    while ((len = Rio_readlineb(&rio, line, MAXLINE)) > 0) {
        Rio_writen(connfd, line, len);
    }
    
    Close(serverfd);
}

Part II：处理多个并发请求

这一部分的任务是实现处理并发请求。

`main`函数

参考书上 P709 的实现。

 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


int main(int argc, char **argv)
{
    int listenfd, connfd;
    char hostname[MAXLINE], port[MAXLINE];
    socklen_t clientlen;
    struct sockaddr_storage clientaddr;

    // 引入线程
    pthread_t tid;

    // 检查命令输入是否正确
    if (argc != 2) {
        fprintf(stderr, "usage: %s <port> \n", argv[0]);
        exit(1);
    }

    // 创建线程
    sbuf_init(&sbuf, SBUFSIZE);
    for (int i = 0; i < NTHREADS; i++) {
        Pthread_create(&tid, NULL, thread, NULL);
    }

    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 connection from (%s, %s)\n", hostname, port);
        // 在循环内部不再是直接执行，而是加入缓冲区
        sbuf_insert(&sbuf, connfd);
    }
    
    printf("%s", user_agent_hdr);
    return 0;
}

同时加入线程执行函数：

1
2
3
4
5
6
7
8
9


// 线程执行函数
void *thread(void *vargp) {
    Pthread_detach(pthread_self());
    while (1) {
        int connfd = sbuf_remove(&sbuf);
        doit(connfd);
        Close(connfd);
    }
}

`SBUF`包

SBUF用于构造生产者-消费者程序，具体实现参考书上 P705-P706 的相关内容。

 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
47
48
49
50
51
52
53
54
55
56


// SBUF 结构体
typedef struct {
    int *buf;          /* Buffer array */         
    int n;             /* Maximum number of slots */
    int front;         /* buf[(front+1)%n] is first item */
    int rear;          /* buf[rear%n] is last item */
    sem_t mutex;       /* Protects accesses to buf */
    sem_t slots;       /* Counts available slots */
    sem_t items;       /* Counts available items */
} sbuf_t;

/* Create an empty, bounded, shared FIFO buffer with n slots */
/* $begin sbuf_init */
void sbuf_init(sbuf_t *sp, int n)
{
    sp->buf = Calloc(n, sizeof(int)); 
    sp->n = n;                       /* Buffer holds max of n items */
    sp->front = sp->rear = 0;        /* Empty buffer iff front == rear */
    Sem_init(&sp->mutex, 0, 1);      /* Binary semaphore for locking */
    Sem_init(&sp->slots, 0, n);      /* Initially, buf has n empty slots */
    Sem_init(&sp->items, 0, 0);      /* Initially, buf has zero data items */
}
/* $end sbuf_init */

/* Clean up buffer sp */
/* $begin sbuf_deinit */
void sbuf_deinit(sbuf_t *sp)
{
    Free(sp->buf);
}
/* $end sbuf_deinit */

/* Insert item onto the rear of shared buffer sp */
/* $begin sbuf_insert */
void sbuf_insert(sbuf_t *sp, int item)
{
    P(&sp->slots);                          /* Wait for available slot */
    P(&sp->mutex);                          /* Lock the buffer */
    sp->buf[(++sp->rear)%(sp->n)] = item;   /* Insert the item */
    V(&sp->mutex);                          /* Unlock the buffer */
    V(&sp->items);                          /* Announce available item */
}
/* $end sbuf_insert */

/* Remove and return the first item from buffer sp */
/* $begin sbuf_remove */
int sbuf_remove(sbuf_t *sp)
{
    int item;
    P(&sp->items);                          /* Wait for available item */
    P(&sp->mutex);                          /* Lock the buffer */
    item = sp->buf[(++sp->front)%(sp->n)];  /* Remove the item */
    V(&sp->mutex);                          /* Unlock the buffer */
    V(&sp->slots);                          /* Announce available slot */
    return item;
}

Part III：缓存Web对象

第3个任务就是实现缓存一些网页对象。

具体地，当我们的代理访问了一个服务器网页的时候，我们需要将这个网页缓存下来，在之后的请求中就不需要再次从服务器那里请求这个网页了。

但是，缓存的大小不是无限的，这就需要我们在缓存使用满的时候驱逐一部分已经缓存的网页出去。本实验要求我们使用LRU（最近最少使用）的方法，也就是找到上一次访问时间最远的对象替换掉。

`main`函数

 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


int main(int argc, char **argv)
{
    int listenfd, connfd;
    char hostname[MAXLINE], port[MAXLINE];
    socklen_t clientlen;
    struct sockaddr_storage clientaddr;

    // 引入线程
    pthread_t tid;

    // 检查命令输入是否正确
    if (argc != 2) {
        fprintf(stderr, "usage: %s <port> \n", argv[0]);
        exit(1);
    }

    // 创建线程
    sbuf_init(&sbuf, SBUFSIZE);
    for (int i = 0; i < NTHREADS; i++) {
        Pthread_create(&tid, NULL, thread, NULL);
    }
    // 初始化缓存
    initCache();

    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 connection from (%s, %s)\n", hostname, port);
        // 在循环内部不再是直接执行，而是加入缓冲区
        sbuf_insert(&sbuf, connfd);
    }

    printf("%s", user_agent_hdr);
    return 0;
}

读者-写者模型

读者-写者模型实现了多个读者可以同时读取，但是读-写、写-写会互斥。在本实验中采用的是读者优先的策略。

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


// 读者-写者模型
void readBegin(Cache *c) {
    P(&c->mutex);
    if (++c->read_cnt == 1) P(&c->w);
    V(&c->mutex);
}

void readEnd(Cache *c) {
    P(&c->mutex);
    if (--c->read_cnt == 0) V(&c->w);
    V(&c->mutex);
}

void writeBegin(Cache *c) {
    P(&c->w);
}

void writeEnd(Cache *c) {
    V(&c->w);
}

缓存相关

缓存结构

1
2
3
4
5
6
7
8


typedef struct Cache {
    bool empty;                 // 是否为空
    URL url;                    // 缓存 URL
    char data[MAX_OBJECT_SIZE]; // 缓存内容
    int lru;                    // 上次访问时间
    int read_cnt;
    sem_t mutex, w;             // 读者-写者模型相关信号量
} Cache;

缓存函数

初始化缓存

1
2
3
4
5
6
7
8


// 缓存初始化
void initCache() {
    for (int i = 0; i < MAX_CACHE; ++i) {
        cache[i].empty = 1;
        Sem_init(&cache[i].mutex, 0, 1);
        Sem_init(&cache[i].w, 0, 1);
    }
}

寻找缓存：枚举每一个缓存，判断是否为空，如果不为空判断URL 是否相等。

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


Cache *getCache(URL *url) {
    Cache *ans = NULL;
    for (int i = 0; i < MAX_CACHE && ans == NULL; ++i) {
        readBegin(&cache[i]);
        if (!cache[i].empty && urlEqual(&cache[i].url, url)) {
            ans = &cache[i];
        }
        readEnd(&cache[i]);
    }
    if (ans != NULL) {
        updateLRU(ans);
    }
    return ans;
}

插入缓存

 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


// 插入缓存
void insCache(URL *url, char *data) {
    Cache *pos = NULL;
    for (int i = 0; i < MAX_CACHE && pos == NULL; ++i) {
        readBegin(&cache[i]);
        if (cache[i].empty) {
            pos = &cache[i];
        }
        readEnd(&cache[i]);
    }
    // fprintf(stderr, "insCache: pos = %#p\n", pos);
    if (pos != NULL) {
        fillCache(pos, url, data);
        return;
    }
    
    int minLRU = __INT_MAX__;
    for (int i = 0; i < MAX_CACHE; ++i) {
        readBegin(&cache[i]);
        if (!cache[i].empty && cache[i].lru < minLRU) {
            minLRU = cache[i].lru;
            pos = &cache[i];
        }
        readEnd(&cache[i]);
    }
    fillCache(pos, url, data);
}

更新 LRU

1
2
3
4
5
6
7


// 更新 LRU
void updateLRU(Cache *c) {
    static int clock = 0;
    writeBegin(c);
    c->lru = ++clock;
    writeEnd(c);
}

装载缓存

1
2
3
4
5
6
7
8
9


// 装载缓存
void fillCache(Cache *c, URL *url, char *data) {
    writeBegin(c);
    c->empty = 0;
    urlCopy(&c->url, url);
    strcpy(c->data, data);
    writeEnd(c);
    updateLRU(c);
}

辅助函数，用来判断URL是否相等和复制URL

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


bool urlEqual(const URL *a, const URL *b) {
    return strcmp(a->host, b->host) == 0 &&
           strcmp(a->port, b->port) == 0 &&
           strcmp(a->path, b->path) == 0;
}

void urlCopy(URL *a, const URL *b) {
    strcpy(a->host, b->host);
    strcpy(a->port, b->port);
    strcpy(a->path, b->path);
}

实验总结

本次的Proxy实验可以看作是对I/O、网络编程和并发编程的一次综合运用。通过实现一个简单却具有重要实际应用价值的网络代理服务器帮助我们回顾了这三部分的基本原理和核心思想。我同时进一步认识到进程（线程）作为计算机系统最成功概念的意义。

在实验过程中，我进一步巩固了LRU算法，同时意识到只要程序涉及到线程的并发运行，就必须考虑到代码的健壮性，这对我今后的学习和实践都具有重要的价值。

Proxy实验

实现网络代理服务器

Part I：实现顺序的代理服务器

`main`函数

main函数

解析URL

`readClient`函数

`doit`函数

Part II：处理多个并发请求

`main`函数

引入线程的main函数

`SBUF`包

Part III：缓存Web对象

`main`函数

读者-写者模型

缓存相关

缓存结构

缓存函数

实验总结

Part I：实现顺序的代理服务器

main函数

main函数

解析URL

readClient函数

doit函数

Part II：处理多个并发请求

main函数

引入线程的main函数

SBUF包

Part III：缓存Web对象

main函数

读者-写者模型

缓存相关

缓存结构

缓存函数

实验总结

`main`函数

`readClient`函数

`doit`函数

`main`函数

`SBUF`包

`main`函数