奇怪的 C++ 链表错误

Question

我在不同机器上用不同版本的 GNU 测试了这个代码片段，只有一个奇怪的 Mac 与 Clang 1001.0.46.3 报告分段错误。这段代码是不是有地址问题或者指针问题？

#include <iostream>
#include <vector>

using namespace std;

class Node
{
public:
    Node* next;
    int val;

};

class List
{
private:
    Node* head;
    Node* tail;
public:
    List()
    {
        head = tail = nullptr;
    }
    bool isEmpty()
    {
        if(!head && !tail) return true;
        return false;
    }
    void pushBack(int num)
    {
        Node* newNode = new Node;
        newNode->val = num;
        if(isEmpty()) head = tail = newNode;
        else
        {
            tail->next = newNode;
            tail = tail->next; 
        }
    }

    void pushFront(int num)
    {
        Node* newNode = new Node;
        newNode->val = num;
        if(isEmpty()) head = tail = newNode;
        else
        {
            Node* tmp = head;
            newNode->next = tmp;
            head = newNode;
        }
    }

    void popBack()
    {
        if(head == tail) {delete head; head = nullptr; return;}
        Node* tmp = head;
        while(tmp->next != tail) tmp = tmp->next;
        tail = tmp;
        delete tmp->next;
        tmp->next = nullptr;
    }

    void popFront()
    {
        if(head == tail) {delete head; head = nullptr; return;}
        Node* tmp = head;
        tmp = tmp->next;
        delete head;
        head = nullptr;
        head = tmp;
    }

    int findLen()
    {
        if(isEmpty()) return 0;
        int len = 0 ;   
        Node* tmp = head;
        while(tmp)
        {
            len++;
            //if(tmp == tail) break;
            tmp = tmp->next;
        }
        return len;
    }

    void inserter(int position, int num)
    {
        if(position > findLen() || isEmpty()) return;
        int index = 0;
        Node* tmp = head;
        Node* newNode = new Node;
        newNode->val = num;
        if(position == 0) {pushFront(num); return;}
        else if(position == findLen()) {pushBack(num); return;}
        while(tmp->next)
        {
            index++;
            if(index == position)
            {
                Node* tmp2 = tmp->next;
                tmp->next = newNode;
                newNode->next = tmp2;
                return;
            }   
            tmp = tmp->next;
        }
    }

    void print()
    {
        if(isEmpty()) return;
        cout << "list = ";
        Node* tmp = head;

        while(tmp)
        {
            cout << tmp->val << " ";
            if(tmp == tail) break;
            tmp = tmp->next;
        }
        cout << endl;
    }
};



int main()
{   
    cout << "delete added" << endl;
    List testList;
    testList.pushBack(5);
    testList.pushBack(10);
    testList.pushBack(15);
    testList.pushBack(20);                          // after this line, we got segmentation fault
    cout << "len = " << testList.findLen() << endl;
    testList.print();

    testList.pushFront(5);
    testList.pushFront(10);
    testList.pushFront(15);
    testList.pushFront(20);
    cout << "len = " << testList.findLen() << endl;
    testList.print();

    testList.inserter(0,8);
    cout << "len = " << testList.findLen() << endl;
    testList.print();

    testList.inserter(9,555);
    cout << "len = " << testList.findLen() << endl;
    testList.print();

    testList.inserter(5,333);
    cout << "len = " << testList.findLen() << endl;
    testList.print();

    cout << "popBack" << endl;
    testList.popBack();
    cout << "len = " << testList.findLen() << endl;
    testList.print();

    cout << "popFront" << endl;
    testList.popFront();
    cout << "len = " << testList.findLen() << endl;
    testList.print();

    cout << "popBack" << endl;
    testList.popBack();
    cout << "len = " << testList.findLen() << endl;
    testList.print();

    cout << "popFront" << endl;
    testList.popFront();
    cout << "len = " << testList.findLen() << endl;
    testList.print();

    return 0;
}

跟进：嘿，伙计们，我刚刚自己得到了一些线索。我觉得问题应该出在OS这边。检查相关的汇编代码后，我注意到即使局部变量的默认初始化值为 0，但它们并不总是零。我觉得问题应该出在OS的分页方案上。我将尽力弄清楚MacOS（内核10.15.1）和linux如何选择页面以及如何为局部变量生成随机值。如果有人知道这个领域或有任何线索可以弄清楚，请随时告诉我。干杯。

Answer 1

你的问题是在每个 Node 中 next 成员没有被初始化。

取消注释您的注释行 //if(tmp == tail) break; 在方法 findLen 中也是一个解决方案。

解决此问题的正确方法是将您的节点 class 重写为

class Node
{
public:
    Node* next = nullptr;
    int val;

};

无论如何，我希望这只是家庭作业或练习，否则就去做吧std::list。

Answer 2

I think next would be initialized as nullptr by default.

默认情况下，只有静态存储是零初始化的，即使没有任何显式初始化程序也可以安全读取。

动态和自动存储可以而且确实可以保存随机垃圾（理论上和实际实现中）。

实际上，前几个动态分配也可能是零初始化的，因为分配器必须从 OS 中获取新页面。但是在删除一些对象并分配更多对象之后，您正在从空闲列表中回收内存。（除非 CRT 启动代码已经在 main 顶部之前执行了该操作，在这种情况下，即使是第一个小分配也会获得脏内存。）

valgrind 等工具可以帮助识别读取未初始化的内存。

MSVC 的调试模式对此也有一个有用的特性：它用可识别的有害值填充 "uninitialized" 变量，memset(0xCC) 不是有效指针，并且（如果作为 x86 机器执行）代码）是一个 int3 指令：调试断点。在其他情况下（比如整数）往往是可识别的。

After check the related assembly code, I noticed that even though I got default initialized value as 0 for local variables, they are not ALWAYS zero. I think the problem should be the paging scheme of the OS.

来自 OS 的匿名内存的新页面始终清零，以避免在用户之间泄露潜在的敏感信息。（例如，以前用于读取 /etc/shadow 或 ssh 密钥内容的页面）。这适用于 new 必须在幕后使用 mmap 或 brk 以获得更多内存，或者 第一次 函数调用递减 RSP 的时间进入新页面。

通常你没有得到一个新的页面，你正在重用一个已经分配的页面（通过空闲列表，或者通过重用之前函数调用脏的内存来为堆栈）。除非您的函数是调用堆栈中最深的，否则会出现脏内存。

您的实验在未初始化的变量中看到大部分为零，这可能是您的程序所做的唯一事情，因此是第一次调用堆栈如此深。

或者对于动态分配，可能在空闲列表中没有脏内存，所以 new 不得不从 OS.
中获取一个新的虚拟页面

页面大小仅决定何时逻辑零堆栈和 BSS 物理清零，以及粒度如何。

根据对另一个答案的评论，我认为您对 OSes 用来进行归零的机制很感兴趣。 "Getting more pages" 作为一个概念是有道理的，对于考虑动态存储很有用，但会让您对堆栈感到困惑。

静态存储和堆栈space有固定的布局。函数调用的堆栈帧位于其父级帧的正下方，并在 returns 时被释放。调用栈是一个栈数据结构。

因此，重要的是这是否是您进入堆栈的最深阶段；页面边界无关紧要。一个函数在运行时不会弄脏整页堆栈space，它只会弄脏它实际使用的内存。堆栈通常限制为 8 MiB，在 CRT 开始代码调用时只有少数 4k 页被使用 main。因此，您基本上将 8MiB 归零内存数组的大部分作为堆栈 space.

奇怪的 C++ 链表错误

Weird C++ linked list bug

c++

macos

paging

x86

segmentation-fault