CS144-check1

overview

需要我们构造一个神奇的类Reassembler，接受无序的substring，并在该类中恢复其顺序。capacity我认为为bytestream的buffer的capacity，available_capacity我认为为bytestream的available_capacity，下文称为有效区

process

刚完全理解时，觉得还挺简单的，具体的思路为，用一个链表将接收的substring收集起来，按照substring首个字节的index从小到大排序，每次收到一个first_index等于next_byte的substring，先将substring放进链表，接着update整个链表，具体地，将已经排好的连续的substring推入bytestream。想法很美丽，但现实是很苍白的。以下是我在面向测试编程时发现自己没考虑到的点：

  • 我们需要支持substring的first_index小于next_byte的情况，如果该substring有在有效区的部分，还需要写入而不能直接丢掉。

  • 写入有效区的substring超出有效区的部分需要删除，但其保留的元素不能带有is_last_substring，否则会导致提前结束。

  • 有效区内随时支持覆写(overlap)，只要该部分还没被推入buffer，就可以修改。

  • pending也是得支持overlap，对于覆写的部分不能重复统计。

当我兴奋地发现代码通过前面的所有测试，准备安心下班时，最后一个测试居然报错了，说是读出来的数据和写入的不一样？？？？

由于之前的代码已经是屎山级别，难以辨认出问题，并且难以调试，因为数据量巨大，决定重写，以下为重写代码：

success implement

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

class Reassembler
{
...
private:
  ByteStream output_; // the Reassembler writes to this ByteStream
  uint64_t next_byte{}; // store the next byte's index aka. first unassembled index
  class substring
  {
    public:
    std::string data{};
    uint64_t first_byte{};
    bool is_last_substring{};
  };
  std::list<substring> substrings{};
  uint64_t unaccept_index(); // return the first unacceptable byte index 
  uint64_t unpopped_index(); // return the first unpopped byte index
  uint64_t finish_index = 0xfffffffff;
  void update(substring &st); // scan the area and push all continous bytes in bytestream
};

以上为reassembler中的类以及成员：

  • next_byte：用于记录第一个不确定顺序的位置
  • substrings：用于存放substring的列表，用list是因为我希望进入的substring可以按照first_byte的大小，从小到大顺序排放，并且支持快速的插入、删除，双向链表符合这些要求。
  • unaccept_index：第一个无效的位置。
  • finish_index：结束的位置，初始化为大数，主要用来避免空字符串放在首位且并非结束的情况。
  • update：用于更新substrings列表，后文会介绍

接下来是最复杂的部分，以及我的详细解决思路：

insert

在insert中，将接收到的substring进行处理，我们接收到的substring无非就以下几种：

  • 完全不在有效区内：直接抛弃（注意有效区为0时需要特别判断）
  • 存在一部分小于next_byte，这样的裁掉头部就行
  • 存在一部分大于等于unaccept_byte，这样的裁掉尾部，注意裁掉尾部时，需要修改substring的is_last_substring的信息，因为裁掉尾步后，这个substring就不是最后一个了。

注意是可能同时裁掉头部和尾部的！

明确类型，我们对应地进行处理就行，并将处理后的substring（如果不抛弃）放入我们的列表中（使用update传入substring），重活全部丢给update

update

注意在调用update之前，有一件事是确定的：此时列表里面不存在任何重叠（因为每次update都会处理重叠）

update的过程分成下面几步：

  • 寻找位置插入st，维持列表仍为按first_byte从小到大排序
  • 检查前一个节点（只用找最近的一个，显然更前面的不会发生重叠）：
    • 如果st已经是列表的最前面，就不用找了
    • 如果st的前一个substring的范围比st大，就丢掉st，以免切割前一个substring变成两部分，更加麻烦
    • 如果st的前一个substring的范围和st不相交，什么都不用做
    • 如果st和前一个substring有重叠部分，裁切前一个substring，避免调整first_byte可能导致的重新排序
  • 检查后一个节点的substring（需要一直往后找，直到发现不重叠的才结束）：
    • 如果st已经是列表的最后面，就不用找了
    • 如果st和substring没有重叠，就直接结束（显然后面的也不会重叠了）
    • 如果st完全包含在substring中（只有两者的first_byte一样才会发生），就抛弃st，同理，substring如果包含在st中，我们也要抛弃substring
    • 如果st和substring有重叠，修改substring（可能修改st会更好，但这也可以过）
  • 检查是否存在已排序完成的部分（全部情况都需要这个检查）。类似消消乐，循环直到发现第一个无法被推入的位置。
  • 检查是否结束

关键源码

重新写过的代码的思路较为清晰，有较为详细的注释。感觉这种码风主要继承于xv6，而不像c++的风格。（虽然用到了一些modern c++）

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
// in reassembler.cc
#include "reassembler.hh"
using namespace std;


void Reassembler::update(substring &st)
{
  // since we will handler overlap every time,
  // we assume overlaping substrings dont exist.

  // 1.find the pos and insert.
  list<substring>::iterator it = substrings.begin();
  list<substring>::iterator backit = substrings.begin();
  list<substring>::iterator fowdit = substrings.begin();

  for(; it != substrings.end(); it++)
    if((*it).first_byte >= st.first_byte)
      break;
  it = substrings.insert(it, st);

  // 2.check the substring before pos.
  if(it != substrings.begin()){
    backit = it;
    backit --;

    substring t = (*backit);
    // case 1: st totally inside the substring. delete the st.
    if((*backit).first_byte + (*backit).data.size() >= st.first_byte + st.data.size()){
      substrings.erase(it);
      goto push;
    }

    // case 2: st overlap part of it. edit the substring.
    if((*backit).first_byte + (*backit).data.size() < st.first_byte + st.data.size()){
      (*backit).data = (*backit).data.substr(0, st.first_byte - (*backit).first_byte);
    }

    // case 3: no overlap. do nothing.
  }


  // 3.check the substring after pos.
  if(it == substrings.end())
    goto push;

  fowdit = it;
  fowdit++;
  for(; fowdit != substrings.end();){
    // case 1: no overlap. 
    if((*fowdit).first_byte >= st.first_byte + st.data.size())
      break;

    // case 2: st totally inside the substring. delete the st.
    if((*fowdit).first_byte == st.first_byte && (*fowdit).data.size() >= st.data.size()){
      substrings.erase(it);
      goto push;
    }

    // case 3: substring totally inside the st. delete the substring.
    if((*fowdit).first_byte + (*fowdit).data.size() <= st.first_byte + st.data.size()){
      fowdit = substrings.erase(fowdit);
      continue;
    }

    // case 4: st overlap part of it. edit the substring.
    if((*fowdit).first_byte + (*fowdit).data.size() > st.first_byte + st.data.size()){
      (*fowdit).data = (*fowdit).data.substr(st.first_byte + st.data.size() - (*fowdit).first_byte);
      (*fowdit).first_byte = st.first_byte + st.data.size();
    }
    fowdit++;
  }

push:
  // 4.scan the list and push possible substrings
  substring t;
  while(!substrings.empty()){
    t = substrings.front();

    if(t.first_byte == next_byte){
      output_.writer().push(t.data);
      next_byte += t.data.size();
      substrings.pop_front();
    } else 
      break;
  }

  if(t.first_byte + t.data.size() == finish_index && substrings.empty()){
    output_.writer().close();
  }

  return;
}

void Reassembler::insert( uint64_t first_index, string data, bool is_last_substring )
{
  // pack it up.
  substring st;
  st.first_byte = first_index;
  st.is_last_substring = is_last_substring;
  st.data = data;

  // get the finish byte index
  if(st.is_last_substring){
    finish_index = first_index + data.size();
  }
  // if the substring totally outside the available area, discarded.
  if(first_index + data.size() < next_byte || first_index >= unaccept_index()){
    return;
  }

  // if no space for substring, discarded.
  if(next_byte == unaccept_index())
    return;

  // if the substring have bytes outside the available area, cut it.
  // case 1: head outbound.
  if(st.first_byte < next_byte){
    st.data = st.data.substr(next_byte - st.first_byte);
    st.first_byte = next_byte;
  }

  // case 2: tail outside.
  if(st.first_byte + st.data.size() > unaccept_index()){
    st.data = st.data.substr(0, unaccept_index() - st.first_byte);
    st.is_last_substring = false;
  }

  // finish process, push into the list.
  update(st);

  return;
}

uint64_t Reassembler::bytes_pending() const
{
  uint64_t used_bytes = 0;
  for(substring i: substrings){
    used_bytes += i.data.size();
  }
  return used_bytes;
}


uint64_t Reassembler::unpopped_index()
{
  return output_.writer().bytes_pushed();
}

uint64_t Reassembler::unaccept_index()
{
  return next_byte + output_.writer().available_capacity();
}

总结/经验

其实第二次写的代码还是在同一个地方出错了，但这次的debug方法是：

在minnow/build的目录下执行：

ctest -R '^reassembler_speed_test$'

查看minnow/build/Testing/Temporary/LastTest.log，搭配上在reassembler.cc中输出的调试信息（上面的源码已经删掉），发现了问题。

期间发现的一些重大错误包括但不限于：

  • backit == it++：忘记了it的值已经改变
  • 在insert中，对于头部尾部都超出范围的处理，与自己的预期不一样，是没用修改后的st来判断导致的。

总用时：2-3天（不熟悉c++导致的）

#Computer-Networking
CS144-check1
https://pactheman123.github.io/2024/09/12/CS144-check1/
作者
Xiaopac
发布于
2024年9月12日
许可协议