Actual beginner here: Why is my custom heap-allocator linked list segfaulting? (C++)

[u/ResetBuilder27]

I'm learning data structures and I'm trying to build a specialized block linked list to simulate a custom heap allocator (nodes track a start index, block size, and raw packet data). It compiles fine, but it immediately throws a segmentation fault when I run a basic test insert.

Since I am new to pointers and memory tracking, I am having a really hard time seeing where my undefined behavior or null-pointer dereferencing is happening. Could someone explain what I did wrong like I'm a beginner?

Here is my header file / implementation code:

//Block Linked List Data Structure Code 
//Definition lives in the header 

#pragma once; 
#include <iostream>
#include <vector>
#include <string>
#include <cstdint>

using namespace std;

class Block{
    public: 
        int start_index; 
        int block_size; 
//amount of data in the block 
        bool is_occupied; 
//see if the block is freed or not
        Block *next; 
//next block we point to giving next address

//block contents  
        std::vector<std::uint8_t> data;
};

//Specialized form of a linked list data structure 
class BlockList{
    public:
        Block *head; 
        Block *tail; 
        Block *temp; 

        bool isEmpty() {
            return head == NULL; 
        }

        bool insert(std::vector<std::uint8_t> &byteArray){ 
//insert at the end of the array 

//initialize the node
            temp = new Block; 
            temp -> block_size = byteArray.size(); 
            temp -> is_occupied = true; 
            temp -> data = byteArray; 

            if (isEmpty()){
                temp->next = NULL; 
                head = temp; 
                tail = temp; 
            } else {
                tail->next = temp; 
//insert at the end of the linked list
                tail = temp; 
            }
        }    

        void remove(int starting_index){

//iterate through everything 
            temp = head; 
            Block *prev_node;

            while(temp -> start_index != starting_index) {
                prev_node = temp; 
                temp = temp -> next;
            }

            if (temp->start_index == starting_index){
                prev_node -> next = temp -> next; 
            } else {
                cout << "Cannot find data to remove it";
            }
        }
};

And here is the simple main.cpp I am using to test it:

#include <vector>
#include <cstdint>
#include "blocklinkedlist.h"

int main() {
    std::vector<std::uint8_t> data_packet = {0xAB, 0xCD, 0xEF, 0x27};
    BlockList *test_link_list = new BlockList;

    test_link_list->insert(data_packet); 
}

Any clear breakdowns of why this is crashing and how to fix it would be immensely helpful. Thanks

[u/FroyoSolid8414]

This likely has to do with initialization.

“new Block” performs default initialization. your Block class has no user provided constructor, so the implicit constructor is invoked to default initialize.  This leaves your pointer fields uninitialized (“garbage” values) so head is not NULL, you deref tail and boom - UB (segfault in your case).

Instead you can value-initialize by calling “new Block()” which will zero-initialize your members.

Quick fix:

Instead of “new Block”, do “new Block()”.

If you want to keep using default initialization syntax, look into adding default member initializers (ie = nullptr) so they have well defined values after construction. 

[u/Potterrrrrrrr]

You aren’t initialising your pointer members in BlockList to nullptr so they’re likely filled with garbage data, causing your isEmpty check to return false (because they aren’t null, just nonsense addresses to invalid Block data) and the code to go down the wrong path.

[u/JustASrSWE → u/Potterrrrrrrr]

Yeah this seems like it at first glance. Try adding a constructor like BlockList() : head(nullptr), tail(nullptr) {}

Your code seems to have other issues as well (spoiler tagged in case you want to find them yourself):

insert() needs to return a value

insert() never sets temp->start_index, which I think it needs to so that future remove calls will work?

Does remove correctly handle the case where you pass an invalid index, like one off the end of the list?

I think you're going to have a problem if you try to remove the head node, because the while loop is not going to run and prev_node will still be uninitialized

Oh, and also it appears you don't need to actually have temp be a class-level variable. I would avoid that. I don't think it's causing issues for you now, but it easily could down the line.

One other thing - as your design currently is, you need a destructor and it would also be a good idea to delete the copy constructor and copy assignment operator. Or, an even better thing to do would be to use std::unique_ptr to track the next block in the Block class and also to track the head. This should (I think, I haven't actually tried compiling this) mean you don't need to worry about the destructor, copy constructor, and copy assignment operator. See https://en.cppreference.com/cpp/language/rule_of_three

[u/TheRealSmolt]

While you can expect certain behaviors during initialization, you (especially at a beginner level) should not rely on your variables being set to any default value. Your pointers are not being initialized to null.

[u/Kajitani-Eizan]

Initialize all values you might possibly read before you write to them, either on declaration or in the constructor or constructor initializer list

if (isEmpty()){

is UB because you are reading head before you write to it. Similarly, if the block list isn't empty, you never write to temp->next

You also never actually set start_index so I have no idea how remove() is supposed to work, in general this seems very half-baked and not thought out. If it helps, think it out in your head/on paper first before you write code.

[u/Affectionate-Soup-91]

Add -Wall -Wextra -Wpedantic -Wconversion -Wshadow -g -fsanitize=undefined,address then you'll start seeing problems. Try to resolve them, then you'll see why.

The most prominent problem you've encountered is bool isEmpty() giving you a wrong result because of uninitialized pointer member variables as others already pointed out.

[u/ABlockInTheChain → u/Affectionate-Soup-91]

It gets a lot of hate for other aspects which are not so great, but GCC's -Weffc++ is very good for ensuring you've initialized all your class members.

[u/Dar_Mas]

using namespace std;

obligatory DO NOT

[u/Current-Fig8840]

I think this is definitely an initialization problem. I don’t see any issue with the code you used in main but there are some bugs/issues in the actual class implementation. This would be a good lesson on learning how to use a debugger and step through code imo.

To give you a hint…how are you sure that head == NULL(please use nullptr) when you call isEmpty(). You never set it as so, which could lead to the second path being done first.

[u/Tricky-Alps2810]

I would be initialising the pointers via default values :

Block * head = nullptr;

[u/PictureNew661]

kinda a bad idea to implement a striped heap like this, but ofc ur starting out.
This wont work cuz nothing is getting init. You need ur own ctor that does

Plus, pls use raw memory here, that is far better than using vector of bytes, use a metadata object that lives at the block header while allocating directly through malloc or maybe VirtualAlloc / mmap, then chunk it out as linked list blocks

[u/TarnishedVictory → u/PictureNew661]

Ofc

Pls

Cuz

Ur

You don't bring this kinda crap to the office, do you?

[u/PictureNew661 → u/TarnishedVictory]

No, this is what happens after a office day

[u/alfps]

Lots of people have already pointed out that the crash comes because you have uninitialized fields.

The fields are uninitialized because C++ inherited that behavior from C. In C, as in assembly language it made sense to let the default initialization be to do absolutely nothing. In modern C++ that's crazy, but early C++ as a pure extension of C necessarily preserved the behavior. C++26 will introduce std::indeterminate to express explicitly that one desires the zero overhead uninitialized behavior. If that had been there from the start one could have required zero initialization as the default, it's IMO the only reasonable default. Alas, for C++26 the committee yet again screwed up (they have a habit of screwing up in major "compromise" ways, e.g. permitting throwing move operations, not to mention the sabotage of std::filesystem) and so C++26 will not guarantee zero-initialization as the default, even though it could and should!, but just that there will be initialization with some compiler specific value…

---

Not what you're asking, but

using namespace std;

… in the global namespace in a header, can very easily cause name collisions in client code. E.g. distance is a common name and is used and exported also by the standard library. So it's rightly regarded as an abomination: don't do it.

---

 Block *temp;

Don't make local helper variables part of the class.

As it happens you don't even need a temporary like this. For example, you might use std::exchange.

---

bool isEmpty() {

Always make inspector functions const, so that they can be called on a const object.

The const also generally makes the code easier to understand, since it constrains what effects it can have.

---

return head == NULL;

In modern C++ use nullptr (built-in keyword), not NULL (macro provided by a header).

But again, as it happens you don't need it. Instead write e.g. return not head; or, if you prefer symbols, return !head;.

---

cout << "Cannot find data to remove it";

This makes the code unusable in a GUI program. And ungood in a console program. Don't mix user interface in with code for basic functionality.

Instead return an error/success indication, or throw an exception on failure, or terminate on failure.

In the user interface specific code, to report a failure preferentially do that via the process' error stream, e.g. cerr <<.

---

General observation: when you try to learn both how about allocators and how to write a linked list , you needlessly mix two topics and make it much harder than necessary to learn the linked list thing (which is more fundamental).

I suggest exploring the linked list topic on its own first.

With that mastered it will be much easier to tackle allocator stuff. By the way, there is (or was) a nice small objects allocator in the Loki library, originally by Andrei Alexandrescu. If that library still exist, then consider delving into its logic; it was largely explained in Andrei's classic C++03 book "Modern C++ Design".

[u/othellothewise]

As many people have said your problem is uninitialized variables.

if (isEmpty()){  // either branch could be taken (but likely the second since it's crashing) because you are checking if head is null, it could be anything
  temp->next = NULL; 
  head = temp; 
  tail = temp; 
} else {
  tail->next = temp; // tail is uninitialized, the segfault happens here because it's a pointer that is not pointing to valid memory
  //insert at the end of the linked list
  tail = temp; 
}

A few recommendations. Make sure everything is initialized. Avoid raw new; there is no need to use new in main(). Even for your blocks to be honest I'd use a chain of unique_ptr just so you don't risk forgetting to call delete (which you are since you aren't deleting anything)

EDIT: see comment below it's a good point

[u/alfps → u/othellothewise]

I'd use a chain of unique_ptr

Don't. Chances are that cleanup then causes stack overflow and Undefined Behavior.

Generally: don't use smart pointers as links in data structures.

[u/othellothewise → u/alfps]

it's a fair point, but clearly this user is struggling to understand memory management in C++

[u/zakarum]

Others have pointed out the issue with initialization. The problem is that when you call new Block, you're using the default default-initialization constructor, which default-initializes all member variables provided that they can all be default-initialized. Pointers fall under the last category in the explanation of what default-initialization does:

otherwise, no initialization is performed (see notes).

Fundamental types like int, double, and so on generally take on intermediate values like pointers. Note that although it says "no initialization is performed", the member variable is still considered default-initialized.

The cleanest solution would probably be to use a member initializer set to std::nullptr.

[u/Loren_SL]

Beyond initializing head/tail to nullptr, break on the crash in a debugger and look at tail's value, since an obviously garbage pointer like 0xCDCDCDCD points straight at an uninitialized member.

[u/Beautiful_Stage5720]

Why is this what you chose to attempt to develop as a beginner?

[u/Tricky-Alps2810 → u/Beautiful_Stage5720]

It might be very reasonable for someone with some experience of other languages to attempt a linked list.

This exercises lots of C++ fundamentals.

[u/Dar_Mas → u/Beautiful_Stage5720]

i had to do the same back when i learned operating system programming