CS144-Lab笔记
date
Apr 7, 2022
Property
slug
CS144_Notes
status
Published
tags
SkillNote
summary
CS144作业笔记~
type
Post
#0-环境配置:使用Docker和VSCode配置环境:#1-Lab0-Solution:作业环境测试:任务0-手动http访问:任务1-发送邮件测试:任务2-完成利用官方提供的socket库, 实现对于任务0的复现:任务3-要求实现一个有序, 容量有限字节流, 支持读写和容量控制:#2-Lab1-Solution任务1-将子串拼接成字节流
#0-环境配置:
使用Docker和VSCode配置环境:
- 使用Docker配置环境:
- 我这里使用的是MacOS, 使用虚拟机并不方便, 在Docker Hub看到有人配置好了CS144的Docker环境, 直接在pull下来即可使用, 相关参考链接如下:
- MacOS下Docker安装:
- 使用VSCode实现基于Docker开发:
- Docker镜像的pull;
- 利用Docker所pull的镜像创建一个Container, 并Run启动Container;
- 在VSCode中安装Docker和Remote Container的插件;
- 连接使用Docker;
- 在这里最好使用Docker外部挂载文件的方式, 方便后续的文件管理, 不过因为此次项目很小, 我就直接在容器中直接Git Clone文件了, 以后要注意一下;
- VSCode+Docker开发环境配置-参考链接:
- 使用的Docker Image链接:
- 作业环境配置:
- 这里我是在容器内git clone 官方的项目;
cd
至目标环境的位置;- 官方CS144的Github链接如下:
- 直接在目标地址中
git clone
即可: - 把clone下来的项目, 创建成为自己的private项目:
- 先在Github网页版中, 新建一个自己的
private
项目; - 进入到clone下来的文件夹中, 如上述是clone了sponge文件夹, 就cd进入到sponge文件夹中;
- 删除clone下来的git init信息:
rm -rf .git
; - 初始化git init信息:
git init
; - 把路径下的所有文件都添加到git中:
git add .
; - 创建第一次commit:
git commit -m "first commit”
; - 创建一个branch, 这里使用main:
git branch -M main
; - 添加到目标git仓库中:
git remote add origin
https://github.com/lintheyoung/CS144.git
; - 把本地的改变或是文件推送上去:
git push -u origin main
;
git clone https://github.com/CS144/sponge
#1-Lab0-Solution:
作业环境测试:
- 在本地的终端中找到刚才所pull下来, 并目前正在run的Container, 后面会主要操作CONTAINER ID:
docker ps -a
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2F43dc7bda-86e1-48d9-8e17-3efe45d6f33f%2Fa345a96d-fb1e-4ca7-b7c6-999bcf8f14cb%2FUntitled.png%3Ftable%3Dblock%26id%3D853970ac-ee53-4d7f-ba30-e48fe170d0b8%26spaceId%3D43dc7bda-86e1-48d9-8e17-3efe45d6f33f%26expirationTimestamp%3D1739224800000%26signature%3D08xPsbn9JVlOmHbIBfbuRkuOAKmAZ8on0I3x7wRJcMA?table=block&id=853970ac-ee53-4d7f-ba30-e48fe170d0b8&cache=v2)
- 进入Container中:
docker exec -it f0812f19f860 /bin/bash
- 测试一下刚才pull下来的Docker环境是否正确, 通讯的测试:
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2F43dc7bda-86e1-48d9-8e17-3efe45d6f33f%2Fe067d72a-cffa-48d4-8ae0-bc93cf5acf79%2FUntitled.png%3Ftable%3Dblock%26id%3Deed38dae-28eb-4562-8e81-5f9068a52e78%26spaceId%3D43dc7bda-86e1-48d9-8e17-3efe45d6f33f%26expirationTimestamp%3D1739224800000%26signature%3D1QjZIuopW79OVItqhsw5oAkMljGwwjax3prhh8AmOmI?table=block&id=eed38dae-28eb-4562-8e81-5f9068a52e78&cache=v2)
任务0-手动http访问:
如官方PDF所示, 依次输入红色下划线相关command, 并在每一次输入后要回车:
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2F43dc7bda-86e1-48d9-8e17-3efe45d6f33f%2Fd3405cc1-d07d-4877-90e7-71110100b520%2FUntitled.png%3Ftable%3Dblock%26id%3D4ae1c7fd-23d1-420b-ba2c-b87bb0c0276d%26spaceId%3D43dc7bda-86e1-48d9-8e17-3efe45d6f33f%26expirationTimestamp%3D1739224800000%26signature%3DbyhuTiyC5n7p-bAnIqn0FZMOrYI6XWRlrTeRALJLh18?table=block&id=4ae1c7fd-23d1-420b-ba2c-b87bb0c0276d&cache=v2)
任务1-发送邮件测试:
这里暂时没做;
任务2-完成利用官方提供的socket库, 实现对于任务0的复现:
- 主要就还是仿照
sponge/doctest/socket_example_2.cc
代码学习下使用的api即可;
webget.cc
中void get_URL(const string &host, const string &path)
如下:
void get_URL(const string &host, const string &path) {
TCPSocket tcpSocket;
tcpSocket.connect(Address(host, "http")); // 创建连接
// 实际在shell写入的command
tcpSocket.write("GET " + path + " HTTP/1.1\r\n" + "HOST: " + host + "\r\n" + "Connection: close\r\n"); // 继承自FileDescriptor的写方法
tcpSocket.shutdown(SHUT_WR); // 告诉服务器我已完成请求
while(!tcpSocket.eof()){ // 读取服务器端返回的数据
cout << tcpSocket.read();
}
tcpSocket.close();
}
任务3-要求实现一个有序, 容量有限字节流, 支持读写和容量控制:
这里主要思路还是采用
deque
的方法, 从deque
的头部写入, 并记录此时所使用的容量. 读取文件时, 从deque
的尾部pop
即可:构造函数, 初始化容量, ByteStream::ByteStream(const size_t capacity)
// 构造函数, 初始化容量
ByteStream::ByteStream(const size_t capacity){
this->_capacity = capacity;
}
往字节流中写入尽可能多的数据, 返回写入成功数据的字节数, 要是输入的data
长度过长, 就只保证小于_capacity
的能被写入, size_t ByteStream::write(const string &data)
// 写方法, 往字节流中写入尽可能多的数据, 返回写入成功数据的字节数
// 要是输入的data长度过长, 就只保证小于_capacity的能被写入
size_t ByteStream::write(const string &data) {
// 开始写入字节流, 在头部插入元素
// 要是此时的_cur_used已经满了, 就只能写入一定的量
// 获得输入的数据的长度
size_t input_len = data.size();
// 判断能够写入多少, 就只能写入最小的一个
size_t write_able_size = min((this->_capacity - this->_cur_used), input_len);
// 然后全部写入
for(size_t i = 0; i < write_able_size; ++i){
// 按照顺序一个一个写入
// 从头部一个一个塞进去
this->_deque.emplace_front(data[i]);
this->_cur_used++;
this->_write_cnt++;
}
return write_able_size;
}
输出(peek
), 弹出(pop
)指定容量的内容, string ByteStream::peek_output(const size_t len)
, void ByteStream::pop_output(const size_t len)
//! \param[in] len bytes will be copied from the output side of the buffer
// 把其中结点给输出
string ByteStream::peek_output(const size_t len) const {
// 输出一定长度的deque内容
stringstream buf;
// deque支持直接按照索引查找
// 其实使用队列并不是很必要, 使用一个数组就好了
for(size_t i = 0, j = this->_cur_used; i < len && j >= 1; i++, j--){
// 从尾部一个一个读取
buf << this->_deque[j - 1];
}
return buf.str();
}
//! \param[in] len bytes will be removed from the output side of the buffer
// 直接把头结点给pop出
void ByteStream::pop_output(const size_t len){
// 直接去除相关的元素
auto cur_used_tmp = this->_cur_used;
for(size_t i = 0, j = cur_used_tmp; i < len && j >= 1; i++, j--){
// deque自己已经给resize过了, 在pop的时候, 是把之前的里面就有的元素(size决定), 给一个一个的pop出来
this->_deque.pop_back();
// 并且要更新目前的使用情况
this->_cur_used--;
this->_read_cnt++;
}
}
读取指定容量的内容, std::string ByteStream::read(const size_t len)
//! Read (i.e., copy and then pop) the next "len" bytes of the stream
//! \param[in] len bytes will be popped and returned
//! \returns a string
// 读取其中长度为len长度的字节
// 只读, 读取一定长度的输入数据
// 在读取之后, 就要将其置为空(pop掉)
std::string ByteStream::read(const size_t len) {
auto str = peek_output(len);
pop_output(len);
return str;
}
一些琐碎的函数:
void ByteStream::end_input(){
// 判断是否已经
this->_is_end = true;
}
// 判断是否结束输入, 返回is_end即可
bool ByteStream::input_ended() const{
return this->_is_end;
}
// 查看当前可从流中读取的最大数量, 返回已用的大小
size_t ByteStream::buffer_size() const{
return this->_cur_used;
}
// 判断是否为空函数, 可以通过已用大小是否为0来实现
bool ByteStream::buffer_empty() const{
return this->_cur_used == 0;
}
// 判断输出是否已经达到结尾, 内存容量为空且输入结束, 则输出已经达到结尾
bool ByteStream::eof() const{
return buffer_empty() && input_ended();
}
// 查看已读
size_t ByteStream::bytes_written() const{
return this->_write_cnt;
}
// 已写函数
size_t ByteStream::bytes_read() const{
return this->_read_cnt;
}
// 剩余的容量
size_t ByteStream::remaining_capacity() const{
return this->_capacity - this->_cur_used;
}
byte_stream.hh
中的class ByteStream
:
class ByteStream {
private:
size_t _capacity = 0; // 容量的大小
size_t _cur_used = 0; // 目前所使用的流量
// TODO deque和queue的区别是什么呢?
// 一定要采用这种{}的初始化方式
std::deque<char> _deque{};
// 就是还要统计历史上一共写入了多少和读出了多少
size_t _read_cnt = 0;
size_t _write_cnt = 0;
bool _is_end = false;
bool _error{}; //!< Flag indicating that the stream suffered an error.
public:
//! Construct a stream with room for `capacity` bytes.
// 构造函数, 构造方法中里面有capacity表示有限字节流的容量, 因此我们需要一个参数表示容量的大小
// 因为是相对于是class private中一个参数, 所有使用capacity_表示
ByteStream(const size_t capacity);
//! \name "Input" interface for the writer
//!@{
//! Write a string of bytes into the stream. Write as many
//! as will fit, and return how many were written.
//! \returns the number of bytes accepted into the stream
// 写方法, 往字节流中写入尽可能多的数据, 返回写入成功数据的字节数
size_t write(const std::string &data);
//! \returns the number of additional bytes that the stream has space for
// 查看剩余容量的方法, 采用容量-已有数据长度的即可实现
size_t remaining_capacity() const;
//! Signal that the byte stream has reached its ending
// 表示输入字节流已经到达末尾, 我们需要一个bool遍历is_end来判断是否结束输入, false表示未结束输入,
// true表示结束输入
void end_input();
//! Indicate that the stream suffered an error.
void set_error() { _error = true; }
//!@}
//! \name "Output" interface for the reader
//!@{
//! Peek at next "len" bytes of the stream
//! \returns a string
// 查看下次字节流中的len长度的字节, 可以利用一个字符串截取从0到len的子字符并返回, 要注意下越界问题
std::string peek_output(const size_t len) const;
//! Remove bytes from the buffer
// 从字节流中移除len长度的字节, 使用字符串删除函数, 对0到len的字符串进行删除, 还是要注意越界问题
void pop_output(const size_t len);
//! Read (i.e., copy and then pop) the next "len" bytes of the stream
//! \returns a string
// 读取len长度的字节, 可以调用前面已经实现的查看与删除函数来实现本函数
std::string read(const size_t len);
//! \returns `true` if the stream input has ended
// 判断是否结束输入, 返回is_end即可
bool input_ended() const;
//! \returns `true` if the stream has suffered an error
bool error() const { return _error; }
//! \returns the maximum amount that can currently be read from the stream
// 查看当前可从流中读取的最大数量, 返回已使用大小即可
size_t buffer_size() const;
//! \returns `true` if the buffer is empty
// 判断是否为空函数, 可通过已用大小是否为0来实现
bool buffer_empty() const;
//! \returns `true` if the output has reached the ending
// 判断输出是否已经达到结尾, 内存中容量为空且输入结束, 则输出已达到结尾
bool eof() const;
//!@}
//! \name General accounting
//!@{
//! Total number of bytes written
// 查看已读, 已读函数, 我们需要额外的两个变量, write_cnt, read_cnt来储存这两个值
size_t bytes_written() const;
//! Total number of bytes popped
size_t bytes_read() const;
//!@}
};
#2-Lab1-Solution
任务1-将子串拼接成字节流
- 要求: 我们要实现一个流重组器, 该模块将字节流的小段(substring)重新组成正确系列的连续字节流. TCP发送方将其字节流分成较短的段(每个子串不能超过1460字节), 以便于每个子串都能装入一个数据报中, 但是网络可能会对这些数据报进行重新排列, 或者丢弃他们, 或者多次发送它们, 接收端必须将这些段重新组装成它们开始时的连续字节流. 在此次实验中, 我们将实现一个流重组器(stream reassenbler), 可以将带索引的字节流碎片重组成为有序的字节流, 重组完的字节流应该被送入如指定的字节流(byte stream)对象_output中.
- 重组器的构造方法, 重组器有容量控制, 其内的字节流(已重组好的和未重组好的), 不能超过容量, 超出部分需要丢弃.
StreamReassembler(const size_t capacity);
- 接收子串, 并将新的连续的字节写入流中, 只写新的, 如果用重合部分则丢弃重合部分, 这里也要注意容量, 超出容量部分要丢弃.
data
: 子串的内容;index
:data
中第一个字节的索引(按顺序排列);eof
:data
的最后一个字节是否为整个流的最后一个字节;void push_substring(const std::string &data, const uint64_t index, const bool eof);
- 访问重组好的字节流:
const ByteStream &stream_out() const { return _output; }
ByteStream &stream_out() { return _output; }
- 已储存但未被重组的字节流:
size_t unassembled_bytes() const;
- 检查重组器是否为空
bool empty() const;
- 要注意的问题:
- 碎片可能交叉或重叠;
- 如果某次新碎片到达后字节流的开头部分被凑齐,那就应当立刻把凑齐的部分立刻写入到
_output
中。即对应讲义中的: - 碎片可能是一个只包含EOF标志的空串;
- LAB0的顺序字节流和LAB1的流重组器各有各的容量限制。流重组器把字节流写满后,只有当字节流腾出空后才能继续写,相当于字节流满时流重组器出口被“堵住”了。同样当流重组器容量满了后自身也无法被写入新数据,此时到来的新碎片只能被丢弃掉。
When should bytes be written to the stream? As soon as possible. The only situation in which a byte should not be in the stream is that when there is a byte before it that has not been “pushed” yet.
- 大致的思路:
- 因为需要按照index排序, 所以最好就是用一棵树储存, 最小堆→红黑树→对应C++11中的
set
容器, 需要set的push做重载, 这里可以使用运算符重载; - 使用
private
的_eof
判断是否收到EOF
标识段; - 在收到新段时, 要和以前的段做合并处理, 就是可能一个段被发送和接收多次, 要把这些多次的给合并下来;
- 合并段时, 可以先采用简单的分情况讨论的方法给合并, 后面再实现优雅的方法;
- 相关的代码:
StreamReassembler::StreamReassembler(const size_t capacity)
: 容量大小;- 把收到的数据给压进去;
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2F43dc7bda-86e1-48d9-8e17-3efe45d6f33f%2F636583b4-ef96-446e-a40d-55275fa15a67%2FUntitled.png%3Ftable%3Dblock%26id%3Dedba02b4-9abc-4f85-b8d4-9fb611fcae4f%26spaceId%3D43dc7bda-86e1-48d9-8e17-3efe45d6f33f%26expirationTimestamp%3D1739224800000%26signature%3DAK6Z-FzKKDf8bzrD9QvFi0wv75sn0HvNOXhrMBBF9Is?table=block&id=edba02b4-9abc-4f85-b8d4-9fb611fcae4f&cache=v2)
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2F43dc7bda-86e1-48d9-8e17-3efe45d6f33f%2F3196252e-5aa7-4469-a0a2-e79ce9c5da39%2FUntitled.png%3Ftable%3Dblock%26id%3Db6212206-c2af-4139-8d7c-cab120de470e%26spaceId%3D43dc7bda-86e1-48d9-8e17-3efe45d6f33f%26expirationTimestamp%3D1739224800000%26signature%3D8MG_Q-vW1_2p_QunhjeYWZLJN7XCMTijByyMZGDl_as?table=block&id=b6212206-c2af-4139-8d7c-cab120de470e&cache=v2)