CS 144: Introduction to Computer Networking, Fall 2020
https://cs144.github.io/My Repo
https://github.com/wine99/cs1...
工作
TCP 接受方接管到乱序且可能重叠的报文段，StreamReassembler 须要将收到的报文段按状况送入 ByteStream (lab0 实现的），或抛弃，或暂存（在适合的时候重组送入 ByteStream）。
留神点：
- 报文段蕴含索引、长度、内容，lab1 的索引从 0 开始增长，不会溢出绕回。
- 任何报文段，包含新收到的和暂存的，只有能够，就应该立即送入 ByteStream（可能须要手动重组和去重叠）。
- 容量的限度如下图所示。
思路
- 用 set 来暂存报文段，依照报文段的 index 大小比照重载 < 运算符。
- 用 _eof 来保留是否曾经收到过有 EOF 标识的段。
- 收到新段时，通过比照新段的 index、length 和 _first_unacceptable，_first_unassembled 对新段进行必要的剪切，而后解决重叠（调用 _handle_overlap）。
- 解决重叠的逻辑：遍历每个暂存段，如果与新段产生重叠，合并暂存段与新段（调用 _merge_seg，总是往新段上合并，合并后删除重叠的暂存段）。
- 合并段的办法：分类探讨，两个段总共会有四种不同的重叠状况，别离解决。
- 解决完重叠后，调用 _stitch_output：遍历所有暂存段，将可合并的暂存段接入 ByteStream 中。
- 最初，当 _eof 为真且 unassembled_bytes 为 0 时，调用 ByteSteram 的 end_input。
代码
stream_reassembler.hh：
class StreamReassembler { private: // Your code here -- add private members as necessary. ByteStream _output; //!< The reassembled in-order byte stream size_t _capacity; //!< The maximum number of bytes size_t _first_unread = 0; size_t _first_unassembled = 0; size_t _first_unacceptable; bool _eof = false; struct seg { size_t index; size_t length; std::string data; bool operator<(const seg t) const { return index < t.index; } }; std::set<seg> _stored_segs = {}; void _add_new_seg(seg &new_seg, const bool eof); void _handle_overlap(seg &new_seg); void _stitch_output(); void _stitch_one_seg(const seg &new_seg); void _merge_seg(seg &new_seg, const seg &other); public:stream_reassembler.cc：
留神 _add_new_seg 中对于 EOF 的解决细节。
#include "stream_reassembler.hh"// Dummy implementation of a stream reassembler.// For Lab 1, please replace with a real implementation that passes the// automated checks run by `make check_lab1`.// You will need to add private members to the class declaration in `stream_reassembler.hh`template <typename... Targs>void DUMMY_CODE(Targs &&... /* unused */) {}using namespace std;StreamReassembler::StreamReassembler(const size_t capacity) : _output(capacity), _capacity(capacity), _first_unacceptable(capacity) {}//! \details This function accepts a substring (aka a segment) of bytes,//! possibly out-of-order, from the logical stream, and assembles any newly//! contiguous substrings and writes them into the output stream in order.void StreamReassembler::push_substring(const string &data, const size_t index, const bool eof) { _first_unread = _output.bytes_read(); _first_unacceptable = _first_unread + _capacity; seg new_seg = {index, data.length(), data}; _add_new_seg(new_seg, eof); _stitch_output(); if (empty() && _eof) _output.end_input();}void StreamReassembler::_add_new_seg(seg &new_seg, const bool eof) { // check capacity limit, if unmeet limit, return // cut the bytes in NEW_SEG that will overflow the _CAPACITY // note that the EOF should also be cut // cut the bytes in NEW_SEG that are already in _OUTPUT // _HANDLE_OVERLAP() // update _EOF if (new_seg.index >= _first_unacceptable) return; bool eof_of_this_seg = eof; if (int overflow_bytes = new_seg.index + new_seg.length - _first_unacceptable; overflow_bytes > 0) { int new_length = new_seg.length - overflow_bytes; if (new_length <= 0) return; eof_of_this_seg = false; new_seg.length = new_length; new_seg.data = new_seg.data.substr(0, new_seg.length); } if (new_seg.index < _first_unassembled) { int new_length = new_seg.length - (_first_unassembled - new_seg.index); if (new_length <= 0) return; new_seg.length = new_length; new_seg.data = new_seg.data.substr(_first_unassembled - new_seg.index, new_seg.length); new_seg.index = _first_unassembled; } _handle_overlap(new_seg); // if EOF was received before, it should remain valid _eof = _eof || eof_of_this_seg;}void StreamReassembler::_handle_overlap(seg &new_seg) { for (auto it = _stored_segs.begin(); it != _stored_segs.end();) { auto next_it = ++it; --it; if ((new_seg.index >= it->index && new_seg.index < it->index + it->length) || (it->index >= new_seg.index && it->index < new_seg.index + new_seg.length)) { _merge_seg(new_seg, *it); _stored_segs.erase(it); } it = next_it; } _stored_segs.insert(new_seg);}void StreamReassembler::_stitch_output() { // _FIRST_UNASSEMBLED is the expected next index_FIRST_UNASSEMBLED // compare _STORED_SEGS.begin()->index with // if equals, then _STITCH_ONE_SEG() and erase this seg from set // continue compare until not equal or empty while (!_stored_segs.empty() && _stored_segs.begin()->index == _first_unassembled) { _stitch_one_seg(*_stored_segs.begin()); _stored_segs.erase(_stored_segs.begin()); }}void StreamReassembler::_stitch_one_seg(const seg &new_seg) { // write string of NEW_SEG into _OUTPUT // update _FIRST_UNASSEMBLED _output.write(new_seg.data); _first_unassembled += new_seg.length; // both way of updating _FIRST_UNASSEMBLED is ok // _first_unassembled = _output.bytes_written();}void StreamReassembler::_merge_seg(seg &new_seg, const seg &other) { size_t n_index = new_seg.index; size_t n_end = new_seg.index + new_seg.length; size_t o_index = other.index; size_t o_end = other.index + other.length; string new_data; if (n_index <= o_index && n_end <= o_end) { new_data = new_seg.data + other.data.substr(n_end - o_index, n_end - o_end); } else if (n_index <= o_index && n_end >= o_end) { new_data = new_seg.data; } else if (n_index >= o_index && n_end <= o_end) { new_data = other.data.substr(0, n_index - o_index) + new_seg.data + other.data.substr(n_end - o_index, n_end - o_end); } else /* if (n_index >= o_index && n_end <= o_end) */ { new_data = other.data.substr(0, n_index - o_index) + new_seg.data; } new_seg.index = n_index < o_index ? n_index : o_index; new_seg.length = (n_end > o_end ? n_end : o_end) - new_seg.index; new_seg.data = new_data;}size_t StreamReassembler::unassembled_bytes() const { size_t unassembled_bytes = 0; for (auto it = _stored_segs.begin(); it != _stored_segs.end(); ++it) unassembled_bytes += it->length; return unassembled_bytes;}bool StreamReassembler::empty() const { return unassembled_bytes() == 0; }VS Code 调试办法
测试样例对应的源文件在 ./tests 文件夹中，如下图所示。
对应的可执行文件在 ./build/tests 中。
通常 VSC 的 launch.json 中主动生成了一个名为 debug current file 的 launch targe，它有一个前置工作 C/C++: g++ build active file。仿照该 lanuch targe，能够写一个名为 debug lab test 的 launch targe。如下所示。
launch.json:
{ // Use IntelliSense to learn about possible attributes. // Hover to view descriptions of existing attributes. // For more information, visit: https://go.microsoft.com/fwlink/?linkid=830387 "version": "0.2.0", "configurations": [ { "name": "debug lab test", "type": "cppdbg", "request": "launch", "program": "${workspaceFolder}/build/tests/${fileBasenameNoExtension}", "args": [], "stopAtEntry": false, "cwd": "${workspaceFolder}", "environment": [], "externalConsole": false, "MIMode": "gdb", "setupCommands": [ { "description": "Enable pretty-printing for gdb", "text": "-enable-pretty-printing", "ignoreFailures": true } ], "miDebuggerPath": "/usr/bin/gdb" }, { "name": "debug webget", "type": "cppdbg", "request": "launch", "program": "${workspaceFolder}/build/apps/webget", "args": ["cs144.keithw.org", "/hello"], "stopAtEntry": false, "cwd": "${workspaceFolder}", "environment": [], "externalConsole": false, "MIMode": "gdb", "setupCommands": [ { "description": "Enable pretty-printing for gdb", "text": "-enable-pretty-printing", "ignoreFailures": true } ], // "preLaunchTask": "C/C++: g++ build active file", "preLaunchTask": "build project", "miDebuggerPath": "/usr/bin/gdb" }, { "name": "debug current file", "type": "cppdbg", "request": "launch", "program": "${fileDirname}/${fileBasenameNoExtension}", "args": [], "stopAtEntry": false, "cwd": "${workspaceFolder}", "environment": [], "externalConsole": false, "MIMode": "gdb", "setupCommands": [ { "description": "Enable pretty-printing for gdb", "text": "-enable-pretty-printing", "ignoreFailures": true } ], "preLaunchTask": "C/C++: g++ build active file", "miDebuggerPath": "/usr/bin/gdb" } ]}tasks.json:
{ "tasks": [ { "type": "shell", "label": "C/C++: g++ build active file", "command": "/usr/bin/g++", "args": [ "-g", "${file}", "-o", "${fileDirname}/${fileBasenameNoExtension}" ], "options": { "cwd": "${workspaceFolder}" }, "problemMatcher": [ "$gcc" ], "group": { "kind": "build", "isDefault": true } }, { "type": "shell", "label": "build project", "command": "cd build && make -j8", "args": [], }, ], "version": "2.0.0"}而后就能够在测试源代码中打断点调试。