CS144-Lab笔记

date
Apr 7, 2022
Property
slug
CS144_Notes
status
Published
tags
SkillNote
summary
CS144作业笔记~
type
Post

#0-环境配置:

使用Docker和VSCode配置环境:

  • 作业环境配置:
    • 这里我是在容器内git clone 官方的项目;
      • cd至目标环境的位置;
      • 官方CS144的Github链接如下:
      • 直接在目标地址中git clone即可:
        • git clone https://github.com/CS144/sponge
    • 把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;

#1-Lab0-Solution:

作业环境测试:

  • 在本地的终端中找到刚才所pull下来, 并目前正在run的Container, 后面会主要操作CONTAINER ID: docker ps -a
notion image
  • 进入Container中: docker exec -it f0812f19f860 /bin/bash
  • 测试一下刚才pull下来的Docker环境是否正确, 通讯的测试:
 
notion image

任务0-手动http访问:

如官方PDF所示, 依次输入红色下划线相关command, 并在每一次输入后要回车:
notion image

任务1-发送邮件测试:

这里暂时没做;

任务2-完成利用官方提供的socket库, 实现对于任务0的复现:

  • 主要就还是仿照sponge/doctest/socket_example_2.cc代码学习下使用的api即可;
webget.ccvoid 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 中。即对应讲义中的:
      • 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.
    • 碎片可能是一个只包含EOF标志的空串;
    • LAB0的顺序字节流和LAB1的流重组器各有各的容量限制。流重组器把字节流写满后,只有当字节流腾出空后才能继续写,相当于字节流满时流重组器出口被“堵住”了。同样当流重组器容量满了后自身也无法被写入新数据,此时到来的新碎片只能被丢弃掉。
  • 大致的思路:
    • 因为需要按照index排序, 所以最好就是用一棵树储存, 最小堆→红黑树→对应C++11中的set容器, 需要set的push做重载, 这里可以使用运算符重载;
    • 使用private_eof判断是否收到EOF标识段;
    • 在收到新段时, 要和以前的段做合并处理, 就是可能一个段被发送和接收多次, 要把这些多次的给合并下来;
    • 合并段时, 可以先采用简单的分情况讨论的方法给合并, 后面再实现优雅的方法;
      • notion image
        notion image
    • 相关的代码:
      • StreamReassembler::StreamReassembler(const size_t capacity): 容量大小;
      • 把收到的数据给压进去;

© Lin Deyang 2022 - 2025