诡异bug背后的一些知识

Posted on Edited on In , Views: Symbols count in article: 3k Reading time ≈ 3 mins.

Untitled-NO.1

​ 在构建2D激光雷达模拟器的时候，在某个自定义地图中碰上一个奇怪的bug。当然，我从现在完全弄明白这个问题的角度出发，这个bug一点也不奇怪，反倒是警示我要多查cppreference，使用一个STL提供的工具就要看一份文档。

CPP Reference

Bug 表现

​ 首先我们声明一些记号：

  • A 是一个class，与之对应的容器是std::vector<A>
  • func 是一个函数，大概长这样：void func(const A& a, std::vector<A>& arr)。也就是，传入一个A的常引用，并且传入一个A的容器的引用。

​ func的行为是：根据a，进行计算，有可能往arr尾部push新的A实例。a的来源是：a是一个常引用，但是是这样在外部定义的：

1
2
3
4
5
A& a_ref = arr[id];
for (size_t i = 0; i < arr.size(); i++) {
    //...
    func(a, arr);
}

​ for循环外部的，对arr这个vector内某一已经存在元素的引用。之后，将其传入func中，隐式转换为常引用。这实际上对应了我代码中的：阴影在物体内部的投影。比如一个object，需要先计算内部的有效遮挡边如何被内部其他边遮挡。于是A就相当于是 遮挡边class类型，以上的代码就可以认为是：a_ref是当前进行投影的边，arr中保存了这个object的所有遮挡边，使用func来判定a是否遮挡或者如何遮挡其他遮挡边。见Enigmatisms/LiDAR2DSim🔗定义的函数internalOcclusion。

​ 于是我得到了一个这样的结果：

Figure 1. GDB调试，projectEdge2Edge的输入有问题

​ 其中projectEdge2Edge函数就是func，其中参数src（是一个继承了std::vector<Eigen::Vector2d>的class）就是类型A。src的内容出错了。

​ 当然这个问题的定位费了好阵子gdb，打conditional breakpoint才查到（不得不吹一波vscode的内置调试）。可以看到，src（一条投影边）的第一个点（Eigen::Vector2d）值变得奇怪（很小，不应该有）。我首先就猜测是引用失效了（废话），此后猜测 可能是push_back（在breakEdge中进行了push_back，可以说很隐蔽了，breakEdge没有直接传入src，并且src是个const，要是之前我是不会想到引用失效的）导致了引用失效。于是我做了个这样的事情：

1
2
3
4
5
6
7
8
9
10
11
12
while (heap.empty() == false) {
    size_t top = heap.top();
    heap.pop();
    // Edge& this_edge = edges[top] 	  (删除这一行)
    for (size_t i = 0; i < edges.size(); i++) {
        Edge& eg = edges[i];
        Edge& this_edge = edges[top] 	//(加入这一行)
        if (eg.valid == false || &eg == &this_edge)
            continue;
        projectEdge2Edge(this_edge, obs, eg, heap);
    }
}

​ 由于projectEdge2Edge（func）在执行完push_back之后没有对src（a）有任何后续操作，所以我让引用的设置在for循环中执行，每一次都是最新的引用。这样操作之后果然好了。但是不清楚原因。

原因

​ 我先是问了我佬哥。得到的回复是：

往vector pushback确定可能导致它的引用失效，因为它可能resize 那就换了块内存了

​ emmm。很有道理，我又去查了一波资料[1]：

If the new size() is greater than capacity() then all iterators and references (including the past-the-end iterator) are invalidated. Otherwise only the past-the-end iterator is invalidated.

​ 这个capacity是什么呢？vector是动态分配大小的，之前学数据结构与算法的时候，定义动态数组，当时就需要realloc操作，我当时的实现是每次往背后多加4个空余位置。vector也是动态分配的，从它的类函数shrink_to_fit()可以看出来，据说是：每一次realloc到大于当前元素个数的最小二的幂次。那么，举个例子，当vector原来的size是4时，push_back会导致重新分配内存（应该也伴随内存的移动）。这个很好理解，毕竟加入原来分配的内存块是经过了表映射的，如果连续的空间不足，根据vector的又一特性：

The elements are stored contiguously, which means that elements can be accessed not only through iterators, but also using offsets to regular pointers to elements.

​ 要保证连续的话，只能整个挪动原来存储的东西。而引用？虽然我一直以为，如果是指针的话，指向的地址可能没东西了导致出错，引用应该安全的多，应该就能完全指向vector中的元素吧。可惜并不是，stackoverflow上的佬哥这么解释：

  • Reference, internally is implemented as a constant pointer which is automatically de-referenced.
  • The natural implementation of a reference is indeed a pointer.
  • Though a reference is in reality a pointer, but it shouldn't be used like a pointer but as an alias.

​ 常指针或者指针，编译器为了使得reference的设计更安全，要求必须初始化。也就是说，这个引用指向了一块具体的地址，但是由于reallocation，失效了。Nice.

意外收获

1. 迭代器失效

Figure 2. 迭代器失效情况

​ 我之前还写带代码还把迭代器装在一个容器里，知道很不优雅，但现在知道除了不优雅，还很危险（富贵险中求！！）。

2. std::vector<bool>

std::vector<bool> is a possibly space-efficient specialization of std::vector for the type bool.

​ 最有意思的是，cppreference说，空间节约的目的导致bool vector在内存中可能不是连续的。

​ 并且std::vector<bool>有一个新的方法（有别于其他的vector），叫做flip，可以取反内部所有元素。

Reference

[1] https://en.cppreference.com/w/cpp/container/vector/push_back

[2] How are references implemented internally?