CS144计算机网络 Lab1 | Kiprey's Blog

Kiprey commented 2 years ago

https://kiprey.github.io/2021/11/cs144-lab1/

xiaoxiang10086 commented 2 years ago

图画的真不错！！！！！！！！！！

seven-mile commented 2 years ago

我就是采用了合并重叠字符串的方法，最开始是为了省内存，保证完全取决于有效字节数的线性空间复杂度，结果就是性能糟糕透顶，reassem_capacity 测试要跑 1s，写完lab4跑benchmark，笑死，结果根本都跑不出来。大概知道的是，就算用了 std::string::operator+= 合并字符串，时间复杂度看上去依然是 n^2 的，最后数据量大直接完蛋。博主描述得很清楚，厉害。

Vtracker commented 2 years ago

可以不用map<int,string>存零散字符串，使用一个vector当做环形buffer就好了复杂度降到On

Kiprey commented 2 years ago

可以不用map<int,string>存零散字符串，使用一个vector当做环形buffer就好了复杂度降到On

那该如何判断 vector 中哪些区间已经有了数据，哪些又没有呢？

Vtracker commented 2 years ago

@Kiprey

可以不用map<int,string>存零散字符串，使用一个vector当做环形buffer就好了复杂度降到On

那该如何判断 vector 中哪些区间已经有了数据，哪些又没有呢？

没有的都是用'\0'填充写入的时候一个while(v[startIdx])就好了

Kiprey commented 2 years ago

@Kiprey

可以不用map<int,string>存零散字符串，使用一个vector当做环形buffer就好了复杂度降到On

那该如何判断 vector 中哪些区间已经有了数据，哪些又没有呢？

没有的都是用'\0'填充写入的时候一个while(v[startIdx])就好了

沉思，不太行感觉，因为无法区分这个 \0 是 没有数据，还是 远程发来的 \0。

Vtracker commented 2 years ago

@Kiprey

@Kiprey

可以不用map<int,string>存零散字符串，使用一个vector当做环形buffer就好了复杂度降到On

那该如何判断 vector 中哪些区间已经有了数据，哪些又没有呢？

没有的都是用'\0'填充写入的时候一个while(v[startIdx])就好了

沉思，不太行感觉，因为无法区分这个 \0 是 没有数据，还是 远程发来的 \0。

是的，所以还需要一个bool数组来判断是数据还是空

Kiprey commented 2 years ago

@Kiprey

@Kiprey

可以不用map<int,string>存零散字符串，使用一个vector当做环形buffer就好了复杂度降到On

那该如何判断 vector 中哪些区间已经有了数据，哪些又没有呢？

没有的都是用'\0'填充写入的时候一个while(v[startIdx])就好了

沉思，不太行感觉，因为无法区分这个 \0 是 没有数据，还是 远程发来的 \0。

是的，所以还需要一个bool数组来判断是数据还是空

这倒是。之前实现这块时想的比较复杂，我还看到过有人写树来维护的。

Vtracker commented 2 years ago

@Kiprey

@Kiprey

@Kiprey

可以不用map<int,string>存零散字符串，使用一个vector当做环形buffer就好了复杂度降到On

那该如何判断 vector 中哪些区间已经有了数据，哪些又没有呢？

没有的都是用'\0'填充写入的时候一个while(v[startIdx])就好了

沉思，不太行感觉，因为无法区分这个 \0 是 没有数据，还是 远程发来的 \0。

是的，所以还需要一个bool数组来判断是数据还是空

这倒是。之前实现这块时想的比较复杂，我还看到过有人写树来维护的。

我第一次写也是map写的hhhh，现在重新写一遍能多想些

Kiprey commented 2 years ago

@Kiprey

@Kiprey

@Kiprey

可以不用map<int,string>存零散字符串，使用一个vector当做环形buffer就好了复杂度降到On

那该如何判断 vector 中哪些区间已经有了数据，哪些又没有呢？

没有的都是用'\0'填充写入的时候一个while(v[startIdx])就好了

沉思，不太行感觉，因为无法区分这个 \0 是 没有数据，还是 远程发来的 \0。

是的，所以还需要一个bool数组来判断是数据还是空

这倒是。之前实现这块时想的比较复杂，我还看到过有人写树来维护的。

我第一次写也是map写的hhhh，现在重新写一遍能多想些

捂脸，还是考虑的不够周全。 T_T

seven-mile commented 2 years ago

这不是naive的做法么，写组装器不是为了不预先开个大buffer么？vector 做环形 buffer 还能复杂度正确地扩容吗

Vtracker commented 2 years ago

@seven-mile 这不是naive的做法么，写组装器不是为了不预先开个大buffer么？vector 做环形 buffer 还能复杂度正确地扩容吗 “写组装器不是为了不预先开个大buffer么？” 如果考虑到需要动态分配空间的话，这个方法确实有些问题，可能会有服务器内存攻击。考虑deque之类的也可以。主要是看需求吧

Kiprey commented 2 years ago

这不是naive的做法么，写组装器不是为了不预先开个大buffer么？vector 做环形 buffer 还能复杂度正确地扩容吗

组装器的目的，是为了 把零散的数据按索引依次组装，和 buffer 大不大其实没什么关联。组装器的实现，可以选用 map 来精准保存数据，但问题就在于合并等方式过于繁琐，容易出错（之前调试调了 N 久，吐血）；也可以选用 vector，不过它需要事先分配大 buffer（接收窗口大小通常是 64kB），容易被攻击，但是优点就在于速度快，写起来简单。如果只是出于完成这个实验的目的的话，用 vector 实现我觉得会让自己写的舒服很多。

seven-mile commented 2 years ago

这不是naive的做法么，写组装器不是为了不预先开个大buffer么？vector 做环形 buffer 还能复杂度正确地扩容吗

组装器的目的，是为了 把零散的数据按索引依次组装，和 buffer 大不大其实没什么关联。组装器的实现，可以选用 map 来精准保存数据，但问题就在于合并等方式过于繁琐，容易出错（之前调试调了 N 久，吐血）；也可以选用 vector，不过它需要事先分配大 buffer（接收窗口大小通常是 64kB），容易被攻击，但是优点就在于速度快，写起来简单。如果只是出于完成这个实验的目的的话，用 vector 实现我觉得会让自己写的舒服很多。

嗯，调试到吐血的话，谁又不是呢哈哈。主要是，我指的"大buffer"其实关键并不在大，更重要的是如果不能自适应容量，就只能往大开。不过lab本身没有这么细致的要求。回头读读kernel里的工业级实现是什么……另外刚也想了下deque，感觉有点说法的，因为支持随机访问，但还是不能直接做的。

Kiprey commented 2 years ago

@seven-mile

这不是naive的做法么，写组装器不是为了不预先开个大buffer么？vector 做环形 buffer 还能复杂度正确地扩容吗

组装器的目的，是为了 把零散的数据按索引依次组装，和 buffer 大不大其实没什么关联。组装器的实现，可以选用 map 来精准保存数据，但问题就在于合并等方式过于繁琐，容易出错（之前调试调了 N 久，吐血）；也可以选用 vector，不过它需要事先分配大 buffer（接收窗口大小通常是 64kB），容易被攻击，但是优点就在于速度快，写起来简单。如果只是出于完成这个实验的目的的话，用 vector 实现我觉得会让自己写的舒服很多。

嗯，调试到吐血的话，谁又不是呢哈哈。主要是，我指的"大buffer"其实关键并不在大，更重要的是如果不能自适应容量，就只能往大开。不过lab本身没有这么细致的要求。回头读读kernel里的工业级实现是什么……另外刚也想了下deque，感觉有点说法的，因为支持随机访问，但还是不能直接做的。

可以可以，都是饱经调试痛苦的人hhh。

Vtracker commented 2 years ago

@seven-mile

这不是naive的做法么，写组装器不是为了不预先开个大buffer么？vector 做环形 buffer 还能复杂度正确地扩容吗

组装器的目的，是为了 把零散的数据按索引依次组装，和 buffer 大不大其实没什么关联。组装器的实现，可以选用 map 来精准保存数据，但问题就在于合并等方式过于繁琐，容易出错（之前调试调了 N 久，吐血）；也可以选用 vector，不过它需要事先分配大 buffer（接收窗口大小通常是 64kB），容易被攻击，但是优点就在于速度快，写起来简单。如果只是出于完成这个实验的目的的话，用 vector 实现我觉得会让自己写的舒服很多。

嗯，调试到吐血的话，谁又不是呢哈哈。主要是，我指的"大buffer"其实关键并不在大，更重要的是如果不能自适应容量，就只能往大开。不过lab本身没有这么细致的要求。回头读读kernel里的工业级实现是什么……另外刚也想了下deque，感觉有点说法的，因为支持随机访问，但还是不能直接做的。

deque底层的话应该可以自适应扩容，不过dq的常数级复杂度略高。确实我也需要读下kernel的现在实现方式

derecknowayback commented 2 years ago

“如果装不下，则插入 _unassemble_strs 中并返回”这句是什么意思呀，博主大大。reassembler和_output逻辑上应该是同一个空间，装不下该怎么处理呢？

Kiprey commented 2 years ago

@derecknowayback “如果装不下，则插入 _unassemble_strs 中并返回”这句是什么意思呀，博主大大。reassembler和_output逻辑上应该是同一个空间，装不下该怎么处理呢？

在我的实现中，_unassemble_strs 和 _output 是分开的两个数据结构。其中前者是用来存放尚未被装配的数据，后者是存放已经装配可直接被上层读取的数据。如果新来的数据无法和先前的数据连贯，即两段数据之前存在一些尚未被接受的数据，则新来的数据会被暂时存储在 _unassemble_strs 中。

同时考虑到 _output 的长度是固定的，因此如果上层迟迟不去读取 _output 中的数据，则剩余的装配过程都必须暂停，接收到的所有数据包都必须先存储至 _unassemble_strs 中。

derecknowayback commented 2 years ago

嗷感谢博主大大！我认真看了您的代码，明白了！谢谢你！（正好这篇博文一周年了O(∩_∩)O哈哈~）

陈梦倏 @.***

------------------ 原始邮件 ------------------ 发件人: "Kiprey/Kiprey.github.io" @.>; 发送时间: 2022年11月5日(星期六) 晚上8:56 @.>; @.**@.>; 主题: Re: [Kiprey/Kiprey.github.io] CS144计算机网络 Lab1 | Kiprey's Blog (Issue #82)

@derecknowayback “如果装不下，则插入 _unassemble_strs 中并返回”这句是什么意思呀，博主大大。reassembler和_output逻辑上应该是同一个空间，装不下该怎么处理呢？

在我的实现中，_unassemble_strs 和 _output 是分开的两个数据结构。其中前者是用来存放尚未被装配的数据，后者是存放已经装配可直接被上层读取的数据。如果新来的数据无法和先前的数据连贯，即两段数据之前存在一些尚未被接受的数据，则新来的数据会被暂时存储在 _unassemble_strs 中。

同时考虑到 _output 的长度是固定的，因此如果上层迟迟不去读取 _output 中的数据，则剩余的装配过程都必须暂停，接收到的所有数据包都必须先存储至 _unassemble_strs 中。

— Reply to this email directly, view it on GitHub, or unsubscribe. You are receiving this because you were mentioned.Message ID: @.***>

Traveler03 commented 2 years ago

除了第七个点都过了, 第七个测试点一直报(test 2 - number of RX bytes is incorrect) 怎么解决呢

Kiprey commented 2 years ago

除了第七个点都过了, 第七个测试点一直报(test 2 - number of RX bytes is incorrect) 怎么解决呢

每个测试点都会编译出一个可执行的测试文件，用 gdb 调试一下那个测试文件找找错看看。

Ga1acy commented 1 year ago

为什么不考虑up_idx + up.size() > index + data.size()的情况呀？

Kiprey commented 1 year ago

@Ga1acy 为什么不考虑up_idx + up.size() > index + data.size()的情况呀？

这种实际上是包含于 up_idx + up_data.size() > index 这种情况，即"传入数据前半部分重合，需要进行截断，同时在截断后更新当前 index"。所提到的 up_idx + up.size() > index + data.size() 会使得把传入数据一整个全部截断掉。

具体实现中#L101做出了具体解释，但也可以不看代码，只需简单理解将所提到的这种特殊情况特别处理即可。

niuppp-chy commented 1 year ago

想请教一下博主，请问https://github.com/Kiprey/sponge/blob/33e6ba5ebe92f94fc0a177c2debacb3a04b6e300/libsponge/stream_reassembler.cc#L140 这句话是什么意思呀，看了半天没看懂。

Kiprey commented 1 year ago

@niuppp-chy 想请教一下博主，请问https://github.com/Kiprey/sponge/blob/33e6ba5ebe92f94fc0a177c2debacb3a04b6e300/libsponge/stream_reassembler.cc#L140 这句话是什么意思呀，看了半天没看懂。

计算需要被丢弃的数据包的临界起始索引值，关系如下：


                 _next_assembled_idx            first_unacceptable_idx
                           │                                │
                           │                                │
                           ▼                                ▼
   ┌───────────────────────┬────────────────────────────────┐
   │123456789abcdefghijklmn│    1     2     5      4   5    │
   └───────────────────────┴────────────────────────────────┘

   │                       │                                │
   └►_output.buffer_size()◄┘                                │
                                                            │
   │                                                        │
   └─────────────────────►_capacity◄────────────────────────┘

niuppp-chy commented 1 year ago

@Kiprey

@niuppp-chy 想请教一下博主，请问https://github.com/Kiprey/sponge/blob/33e6ba5ebe92f94fc0a177c2debacb3a04b6e300/libsponge/stream_reassembler.cc#L140 这句话是什么意思呀，看了半天没看懂。

计算需要被丢弃的数据包的临界起始索引值，关系如下：


                 _next_assembled_idx            first_unacceptable_idx
                           │                                │
                           │                                │
                           ▼                                ▼
   ┌───────────────────────┬────────────────────────────────┐
   │123456789abcdefghijklmn│    1     2     5      4   5    │
   └───────────────────────┴────────────────────────────────┘

   │                       │                                │
   └►_output.buffer_size()◄┘                                │
                                                            │
   │                                                        │
   └─────────────────────►_capacity◄────────────────────────┘

啊，终于明白了！！！谢谢楼主^-^

howlKu commented 1 year ago

这个lab做得人头疼，我的思路是拿到data先检查一遍能否写入output，如果有剩下的部分则插入map中，插入时只考虑map中是否已存在当前index为key的元素，然后遍历一遍map，重复上面的步骤，这样可以做到在写入output的时候完成去重，但是unassembled_bytes()这个函数要求在装入map时就已完成去重，我得把我的实现推倒重来了……

howlKu commented 1 year ago

@Traveler03 除了第七个点都过了, 第七个测试点一直报(test 2 - number of RX bytes is incorrect) 怎么解决呢

我也是，请问你找到原因了吗

Shang-fei commented 10 months ago

CS144 要求将 ByteStream + Unassembled_strs 的内存占用总和限制在 Reassember 中构造函数传入的 capacity 大小。你好，这句话应该怎么理解呢，只要字符串new_index不超过first_unacceptable，不都是可以插入到红色区域嘛

Kiprey commented 10 months ago

@Shang-fei CS144 要求将 ByteStream + Unassembled_strs 的内存占用总和限制在 Reassember 中构造函数传入的 capacity 大小。你好，这句话应该怎么理解呢，只要字符串new_index不超过first_unacceptable，不都是可以插入到红色区域嘛

不冲突，first_unacceptable 的值是由 capacity 控制的，不至于过多缓存尚未组装的数据，防止内存爆炸。

Shang-fei commented 10 months ago

@Kiprey

@Shang-fei CS144 要求将 ByteStream + Unassembled_strs 的内存占用总和限制在 Reassember 中构造函数传入的 capacity 大小。你好，这句话应该怎么理解呢，只要字符串new_index不超过first_unacceptable，不都是可以插入到红色区域嘛

不冲突，first_unacceptable 的值是由 capacity 控制的，不至于过多缓存尚未组装的数据，防止内存爆炸。

感谢答复，个人理解为_output.buffer_size() + _unassembled_bytes_num可能会比capacity略大，但有first_unacceptable限制所以不会内存爆炸

Shang-fei commented 9 months ago

大佬，还想请教一个问题，这里的判断是否还有数据是独立的有什么作用呢，假设已经确定该字串没有被完全包含，为什么不能省去该段代码，只是将data插入map中，更新_unassembled_bytes_num。而将更新_next_assembled_idx的任务统一交给后面的for循环呢？

// 判断是否还有数据是独立的， 顺便检测当前子串是否被上一个子串完全包含
    if (data_size > 0) {
        const string new_data = data.substr(data_start_pos, data_size);
        // 如果新字串可以直接写入
        if (new_idx == _next_assembled_idx) {
            const size_t write_byte = _output.write(new_data);
            _next_assembled_idx += write_byte;
            // 如果没写全，则将其保存起来
            if (write_byte < new_data.size()) {
                // _output 写不下了，插入进 _unassemble_strs 中
                const string data_to_store = new_data.substr(write_byte, new_data.size() - write_byte);
                _unassembled_bytes_num += data_to_store.size();
                _unassemble_strs.insert(make_pair(_next_assembled_idx, std::move(data_to_store)));
            }
        } else {
            const string data_to_store = new_data.substr(0, new_data.size());
            _unassembled_bytes_num += data_to_store.size();
            _unassemble_strs.insert(make_pair(new_idx, std::move(data_to_store)));
        }
    }

    /*简化为：
    const string new_data = data.substr(data_start_pos, data_size);
    _unassembled_bytes_num += new_data.size();
    _unassemble_strs.insert(make_pair(data_start_idx, std::move(new_data)));
    */

Kiprey commented 9 months ago

@Shang-fei 大佬，还想请教一个问题，这里的判断是否还有数据是独立的有什么作用呢，假设已经确定该字串没有被完全包含，为什么不能省去该段代码，只是将data插入map中，更新_unassembled_bytes_num。而将更新_next_assembled_idx的任务统一交给后面的for循环呢？

数据是否独立 对应于代码中的 data_size > 0 这个判断条件，意思是在经过上面代码多次的判断和重复部分的截断后，是否仍然存在一些数据是当前 _unassembled_strs 所没有的，如果是则需要将该部分数据保存起来。

data_size <= 0 表示传入的数据完全与之前已经传入的数据重合了，那么此时就无需处理。
关于代码逻辑的省略，这个是可省可不省。这里只是一个对可直接装配数据的加速操作，避免了对 map 进行多次操作。

代码实现是比较多样的，只要能通过 check 都算正确。

Shang-fei commented 9 months ago

@Kiprey

@Shang-fei 大佬，还想请教一个问题，这里的判断是否还有数据是独立的有什么作用呢，假设已经确定该字串没有被完全包含，为什么不能省去该段代码，只是将data插入map中，更新_unassembled_bytes_num。而将更新_next_assembled_idx的任务统一交给后面的for循环呢？

数据是否独立 对应于代码中的 data_size > 0 这个判断条件，意思是在经过上面代码多次的判断和重复部分的截断后，是否仍然存在一些数据是当前 _unassembled_strs 所没有的，如果是则需要将该部分数据保存起来。

data_size <= 0 表示传入的数据完全与之前已经传入的数据重合了，那么此时就无需处理。

关于代码逻辑的省略，这个是可省可不省。这里只是一个对可直接装配数据的加速操作，避免了对 map 进行多次操作。

代码实现是比较多样的，只要能通过 check 都算正确。

非常感谢回答，我采用省略后的代码，并进行了数据是否独立的判断，但是最终check有一个没过，找了一天也不知道问题出在哪里

Kiprey commented 9 months ago

@Shang-fei 非常感谢回答，我采用省略后的代码，并进行了数据是否独立的判断，但是最终check有一个没过，找了一天也不知道问题出在哪里

我确实是有点忘记当初写这段代码的原因了，毕竟时隔两年很多细节都忘记了。也有可能是为了躲某个 check 所以写出了一点奇怪的代码hh。有 check 没过的话就用 gdb 调一下那个 check 二进制文件，拿到标准的输入输出再调试会方便一点。不然硬着头皮比较难顶。

Shang-fei commented 9 months ago

@Kiprey

@Shang-fei 非常感谢回答，我采用省略后的代码，并进行了数据是否独立的判断，但是最终check有一个没过，找了一天也不知道问题出在哪里

我确实是有点忘记当初写这段代码的原因了，毕竟时隔两年很多细节都忘记了。也有可能是为了躲某个 check 所以写出了一点奇怪的代码hh。有 check 没过的话就用 gdb 调一下那个 check 二进制文件，拿到标准的输入输出再调试会方便一点。不然硬着头皮比较难顶。

好的感谢！

Shang-fei commented 9 months ago

@Kiprey

@Shang-fei 非常感谢回答，我采用省略后的代码，并进行了数据是否独立的判断，但是最终check有一个没过，找了一天也不知道问题出在哪里

我确实是有点忘记当初写这段代码的原因了，毕竟时隔两年很多细节都忘记了。也有可能是为了躲某个 check 所以写出了一点奇怪的代码hh。有 check 没过的话就用 gdb 调一下那个 check 二进制文件，拿到标准的输入输出再调试会方便一点。不然硬着头皮比较难顶。

哈哈又打扰你啦，我发现了问题所在，如果没写全，则将其保存起来这里是不对的，多余的部分应该直接抛弃掉。

if (write_num < iter->second.size()) {
                _unassembled_bytes_num += iter->second.size() - write_num;
                _unassemble_strs.insert(make_pair(_next_assembled_idx, std::move(iter- 
                 >second.substr(write_num))));

                _unassembled_bytes_num -= iter->second.size();
                _unassemble_strs.erase(iter);
                break;
            }

但是里恰好又把刚刚插入的剩余字段删除，所以代码整体恰好是正确的。不过把这两个保存剩余字段的代码删除，仍可以通过全部check

Eternal60f3 commented 3 months ago

@Vtracker 可以不用map<int,string>存零散字符串，使用一个vector当做环形buffer就好了复杂度降到On

我借鉴一个大脑的使用deque来做环形buffer, 但是时间比作者的这个慢了差不多一倍 (作者的在我电脑上0.8s, deque 1.57s), 不知道问题出在哪里

Kiprey / Kiprey.github.io

CS144计算机网络 Lab1 | Kiprey's Blog #82