Simulating heap memory in C.

[Gat Pelsinger]

I am trying to simulate a heap memory system in C and maybe later adding a garbage collector. So the plan is (or lack thereof), I have a void pointer called heap which gets malloc-ed some value. Now if I wanted to allocate lets say, an integer 2, it is a lot more complicated as my heap is of type void and I have to manage memory myself and traverse through it manually, not mentioning the hardest part which I don't know how to solve is that how would I even know that there is this variable which which is this much long, when all the variables are of different length? Yes, you guessed it right, multiple data types of data in a single big array. Maybe add some boarders before and after a value to marks its start and end?

[Eigenvektor]

You'll effectively have to write your own replacement function for malloc, that keeps track of additional metadata (internally it'll still use malloc/free to do the actual memory management). You'll have to make sure to never use malloc/free in the regular part of your code and always go through your own method instead.

 

I found an article that might help you get started: https://maplant.com/gc.html

 

I would recommend to stop thinking in terms of "variables of different length" and arrays for your GC. A variable is effectively just a (dereferenced) pointer that points to a region of memory. The type of a variable only determines how many consecutive bytes you're pointing to. An array is multiple consecutive regions of memory. But unlike, for example, an int[] the entries in an array don't have to be the same size.

 

Your GC implementation shouldn't need to care what the memory it hands out is being used for. Meaning it doesn't care if the 200 bytes that have been allocated are used for an int-array, or a char-array, or whatever else. It only needs to care that someone requested a 200-byte chunk of memory, it needs to allocate it, return a pointer to it and keep track of how much memory was allocated and whether it's still in use.

 

If you request a second chunk of memory later on, the GC doesn't need to know or care whether that is independent from the first chunk of memory or related in any way. It just has to ensure it keeps track of everything that's been allocated so far.

[wasab]

I wrote my own dynamic memory allocator back in college. For the assigment, students simply used the regular malloc to simulate a heap, you do a malloc call to get a chunk of heap memory for your own dynamic allocator to play with. If you really wanna reinvent the wheel, the syscall to ask the kernel for a chunk of memory is sbrk in Unix OS which is as barebone as it gets. Btw, many dynamic allocator are open source. You can read their source code online somewhere. 

 

Garbage collector I've no experience. Some can be as simple as reference counting. However in c, you have so much freedom, you can easily break a garbage collector by doing certain things. To do something like this you will probably need to restrict and refrain from using some certain features of the langauge.  

[Gat Pelsinger]

@Eigenvektor @wasab

 

What data structure would be good to keep track of the memory with pointers? The article @Eigenvektor mentioned uses a linked list, but will it be better to use an array list instead?

 

Also, I need memory for keeping this metadata. And so if I really want to use the heap, do I make a different partition of the heap, or maybe can I call my code itself for the allocation if that makes sense?

[Eigenvektor]

1 hour ago, Gat Pelsinger said:

What data structure would be good to keep track of the memory with pointers? The article @Eigenvektor mentioned uses a linked list, but will it be better to use an array list instead?

I would say a linked list is much better here, since it avoids having to grow (and shrink) an array. If you remove an entry from the array, you'd potentially have to shift a large number of entries around to close the gap. With a linked list, you simply change one pointer to point to the new next entry, then deallocate the removed entry.

 

Arrays have better performance when it comes to traversal, but linked lists are faster when it comes to insert/delete operations.

 

1 hour ago, Gat Pelsinger said:

Also, I need memory for keeping this metadata. And so if I really want to use the heap, do I make a different partition of the heap, or maybe can I call my code itself for the allocation if that makes sense?

That sounds like a stack overflow.

 

To allocate memory, you need to add an entry into your linked list. If you used your own method to allocate memory for that entry, the method would need to add an entry into the linked list, which in turn would call the method to allocate memory, which would require calling the method to add an entry into the linked list, which in turn would call the method to allocate memory, … I think you get the idea.

 

It doesn't make too much sense for the GC code to use itself to automatically manage its own memory. The scope in which memory is used and the ownership of the memory is well defined, so you don't need the overhead of GC for the GC itself.

[wasab]

6 hours ago, Gat Pelsinger said:

@Eigenvektor @wasab

 

What data structure would be good to keep track of the memory with pointers? The article @Eigenvektor mentioned uses a linked list, but will it be better to use an array list instead?

What I did was define a struct called it a chunk or block and then linked them in a linked list. Meta data are the first couple bytes in a header and last couple bytes in the footer of the chunk. 

 

Do keep in mind, there will eventually be memory fragmentation. You will want to coalesced unused chunks into larger ones or split large chunk into smaller chunks when asked for memory for efficiency. There are many methods to do this. Some prioritize less fragmentation while others priotize more performance with more fragmentation as trade offs. 

 

 

[Gat Pelsinger]

@Eigenvektor @wasab

 

So here is the plan. I create the memory and assign it to a void pointer. I will have 2 linked lists, one for used memory and other for free memory. The linked list (struct) is going to contain the memory address to that heap content (used / free), size of the block, and pointer to the next list. This linked list can also be called as the metadata.

 

So first, an allocation request arrives from outside. First I need to to initialize these linked lists and create the metadata for this allocation request. I am going to store the contents (allocating this struct on my heap) of the used metadata (which is where I am facing a problem and I will talk about this later) on the first address of the memory, as nothing else is allocated, followed by the metadata of free memory. The head (list node) of the used memory first points to nothing, and the head of the free memory points to the starting address of the memory till the end of the heap as everything is empty. I then have to update these metadata(s) to accommodate for the allocation of this metadata itself and then later for the heap content. The head of the used memory still points to nothing (I got confused for a second. We don't create a new node for the metadata itself. We create metadata to access the heap. And the metadata is already accessible through the linked list, and the head of the linked list is always at the first address), and the head of the free memory is incremented by the size of all this metadata (2 metadata). A new node is opened for the free memory only if anything is deallocated and so there is memory fragmentation, else the head keeps incrementing. We then allocate the actual heap content that was requested at where the head of the free memory points to, increment the head pointer of free memory, change the head pointer of used memory to this location, and do other changes such as make the used memory's first node point to this new heap entity. A new node will be opened for the used memory in further allocations.

 

But I am facing a problem. How do I actually allocate the struct on my heap? If I had used malloc, I think it reads the data members of the struct and allocates each of them individually. I tried doing a similar thing, but that resulted in making all my data members of the struct as pointers and making them point to their allocated memory address on the heap, but the main issue is that I cannot store a memory address on this allocated part of the heap. They are not pointers. They are just memory spaces used to store some value. I am basically using a pointer to point to a memory address which again points to another memory address, but a memory address can't point to another memory address. Regarding this, ChatGPT did give me a suggestion that I think works, but I am too tired to understand its language so it would be good if someone explained what is being done. Only read the last conversation and code sent, that is the only thing important, rest nothing is important - https://chat.openai.com/share/27720dc5-4f75-49ca-8f2c-434ce16f207c.

[Eigenvektor]

On 1/8/2024 at 6:52 PM, Gat Pelsinger said:

I am basically using a pointer to point to a memory address which again points to another memory address, but a memory address can't point to another memory address.

A pointer is simply a numeric value, that is interpreted as a memory address. The data behind that memory address can, in turn, be interpreted as a memory address. So yes, you can have a memory address (or rather the data behind that memory address) point to another memory address.

 

In C lingo that would be, for example, a void**, but could just as well be an int** or a long**.

 

On a fundamental level there is no difference between an int16_t*, an int32_t*, an int64_t* or a void*. They are all pointers that point to some memory address. The distinction comes from how you interpret the data behind that address.

 

If you use int16_t* what you're saying is: I'm interested in 16 bit behind that address, and I want to interpret those as a signed integer. If you use int32_t* the pointer works exactly the same way, the only thing that changes is that you're now using 32 bit behind that memory address. The size of the pointer itself is the same in both cases, e.g. a 32 or 64 bit, depending on whether you're running in a 32 bit or 64 bit environment.

 

What sets a void* apart is that it carries no such information. This means it points to a memory address, the same way int16_t* would, but it doesn't specify how to interpret the data at that address or how much data there is. Using a void pointer only makes sense if the information at that address has no fixed structure or the structure doesn't matter for your use case.

 

You could, for example, use malloc to reserve 32+64 bit, then write size information into the first 32 bit behind that memory address, then another memory address into the remaining 64 bit. But that is difficult, since you can't modify a void*, since it carries no size information. That's where the struct comes in.

 

If you have a look at the link I gave you, you can see that the author never works with void pointers directly. He reserves memory for his struct, then immediately casts the pointer he receives from void* to header_t*, because that's the intended use of the memory he reserved.

 

By defining a struct, he defines how the memory he reserved is intended to be used. Just as in16_t* says: "this pointer points to 16 bits of data", a header_t* says "this pointer points to an integer value, followed by another pointer/memory address".

typedef struct header {
    unsigned int    size;
    struct header   *next;
} header_t;

 

To reserve memory for his structure, he uses sizeof() to calculate the necessary number of bytes:

vp = sbrk(num_units * sizeof(header_t)))

sbrk and malloc return void pointers because they can't know/don't need to know what you intend to do with the memory you've reserved. That doesn't mean you should keep working with it. Cast it to a pointer of the type you intend to work with/want to store at that memory address.

 

The data you want to put there is well defined (i.e. the struct). In other words, cast it to header_t*, so that you can conveniently set the data at the memory address the pointer is pointing to.

header_t *up;
up = (header_t *) vp;
up->size = num_units;

 

[Gat Pelsinger]

@Eigenvektor Thanks for the comment, I wouldn't think you would get so involved to help me. But I got past the question I had. Looks like it boils down to not having information of how C backend works. For my understanding right now, the way you allocate a struct on any heap (or even on the stack the same way) is after you have created the pointer, you do p->var = something, which allocates the memory for var I think?

 

The problem I am facing right now, is about getting free memory from memory fragmentation. The situation is, my heap in total has enough memory to accommodate for the allocation request and its metadata, but there is no contiguous block of memory that can hold this allocation request. This is a problem because my alloc function returns a pointer to the block of memory requested and in the behind is a size till which the pointer is allowed to travel till (although that doesn't stop the outside code to still go out of bound and crash the program). To handle this, I have 2 ways, either to defragment the whole heap to get one contagious block of memory which is quite computationally expensive, or to handle memory fragmentation. I don't know how can I get past the second method. For this, I probably have to return a main pointer which points to memory fragments (essentially, creating another linked list in my metadata), and it is upon the outside code to use this fragments. But there are still problems where if one fragment of memory is not enough to store one variable or any entity that the outside code wants or there is left over memory and it is also very risky for the outside code to handle such things. How does malloc get over this?

[Eigenvektor]

5 hours ago, Gat Pelsinger said:

Looks like it boils down to not having information of how C backend works.

C does not have a "backend". When you compile your program, it gets translated into machine code. That code runs directly on the computer's CPU. In other words: You don't have a sufficient enough understanding of how C itself works.

 

There is no runtime and no interpreter between you and the computer's hardware. There's (almost) nothing that prevents you from doing potentially dangerous things like writing to memory you don't own.

 

There is one small exception: Unless your program runs with the highest privileges (ring 0), some resources are off-limits. It can't access these directly and will instead have to communicate with the kernel, or more typically with an OS API that sits on top of the kernel, to get access. This is used to enforce access permissions and prevents, for example, read/write access to files the current user doesn't own.

 

5 hours ago, Gat Pelsinger said:

For my understanding right now, the way you allocate a struct on any heap (or even on the stack the same way) is after you have created the pointer, you do p->var = something, which allocates the memory for var I think?

You're looking at this the wrong way around. You don't create a pointer, you declare a variable of type pointer (e.g. void *pointer). A variable on its own is nothing but a name. It's an abstraction that you can use to conveniently refer to the contents of the memory region it is associated with.

 

You reserve memory by an appropriate system call (e.g. malloc). Under the hood malloc calls the appropriate OS level API to request some memory from the OS. The operating system then reserves memory for use by your program. It then returns the memory address that points to the start of the memory region that is now reserved for your use.

 

malloc then stores that memory address in the variable (or rather the memory associated with that variable) you've previously declared. That makes it possible for you to refer to either the memory region the pointer points to (pointer) or the contents of that memory region (*pointer).

 

Since malloc has no idea what you intend to do with the memory you've reserved, it returns a raw pointer (void*). It's up to you to define how you want to use that memory.

 

To do that, you create a struct. A struct is simply a way to "communicate" with the compiler what you intend to do. So let's declare the structure:

typedef struct header {
    unsigned int    size;
    struct header   *next;
} header_t;

 

This structure doesn't do anything other that say: I want to be able to use a custom type called "header_t". This type consists of a number, followed by a pointer (more technically: "I want to treat the first x bits of memory as an integer and the following x bits as a memory address").

 

To use the struct, you first need to declare a variable of the appropriate type:

header_t *up;

 

This reserves some memory (on the stack) that can hold a memory address. But it does not reserve memory associated with that address nor does it point to anything useful out of the box. So next you need to reserve memory (on the heap) to hold the actual data you want to work with. You use sizeof to reserve the appropriate amount of memory:

void_pointer = sbrk(sizeof(header_t)))

This reserves the appropriate amount of memory, then updates the pointer so that it now holds the memory address of the memory you reserved on the heap.

 

Since you don't want to work with a raw pointer, you cast it to the appropriate type

up = (header_t *) void_pointer;

 

This allows you to modify the bits associated with "size" and "next" by dereferencing the pointer. This is what the arrow (->) is for. Since you're not working with "flat" memory like you would do with e.g. an int* you need some way to address the individual values inside your struct:

// This modifies the pointer itself, e.g. the pointer will move forward
// by an appropriate number of bytes to point to the memory region following
// your struct.
up++;

// This modifies the contents of the memory region your pointer is pointing to
*up = <some value>;

// This modifies a specific value inside the memory region your pointer is pointing to
up->size = <some value>;

 

5 hours ago, Gat Pelsinger said:

But there are still problems where if one fragment of memory is not enough to store one variable or any entity that the outside code wants or there is left over memory and it is also very risky for the outside code to handle such things. How does malloc get over this?

It doesn't. The operating system's memory manager does. As I said above, malloc simply calls the operating system to request memory. The operating system reserves the memory and returns a pointer to it.

 

As I mentioned in a previous answer, modern operating systems run in protected mode. In this mode the memory address you receive isn't associated with any actual physical location in memory. Your program has a virtual address space that the OS maps to some physical location, either in memory on in swap.

 

This allows the OS to move stuff around as it sees fit, without having to update your pointer. It only needs to update its translation table that converts your "virtual" pointer to an actual physical location. This allows it to move data in and out of RAM. It can also move stuff around in memory to consolidate smaller memory fragments into larger contiguous blocks. So for example when you free a small block of memory, it might move other data around to close that gap.

 

Your program doesn't notice any of this because it always addresses the memory with the pointer it has been given when the memory was reserved. The OS handles the translation of this virtual memory address into the actual current physical address it refers to (might be RAM, might be swap…)

[Gat Pelsinger]

@Eigenvektor 

 

I am not getting memory from the OS every time an allocation request is made. That is the whole point of my heap memory program, that it pre-allocates a pool of memory. So after the pool is made, the OS virtual memory mapping doesn't even come in, because I have a private sector of memory which I have to manage with my own pointers.

 

So, after deallocations have been made and there are memory fragments, if I now don't have any contiguous block of free memory, I need to get free memory from the fragments. And as I said earlier, this can be done by 2 methods. One is to defragment the heap to get one large chunk of contiguous memory, which either might not be the most efficient way or it is the only way, and the second method is to allocate data in fragments. This method has many problems though. First, I need to create another linked list which connects all the memory fragments, and put all this work of traversing the fragments onto the outside code which is a mess, and upon that who knows how the outside code wants treat the memory and if one fragment is not enough to store one entity and there now even more mess.

 

EDIT - Well I just realized, even the defragmenting method doesn't work, because I already gave the pointers pointing the blocks of memory and I cannot modify them. Maybe I can make those pointers point to a pointer which I can control? This way I can modify the pointer which I chose to defrag the heap and so the pointer which outside code has also gets updated. Tell me if this is good or maybe I might need to create my own virtual space address or something, and if so, tell me how I can code such a thing.

 

EDIT 2 - So apparently, one way is to use a fixed chunk system for my memory allocater to reduce fragmentation? This will result in underutilization of memory sometimes.

[wasab]

On 1/10/2024 at 4:33 PM, Gat Pelsinger said:

 

EDIT 2 - So apparently, one way is to use a fixed chunk system for my memory allocater to reduce fragmentation? This will result in underutilization of memory sometimes.

Nonono. You are hopelessly confused. Are you getting all of these from chatgpt? Please put that thing away. Trust me, AI is not as good as you think, my company does generative ai and that thing acts with an IQ of a 4 year old toddler at best of times.

 

Understand the theory first. It feels like you are rushing to drive a car without understanding what a gas pedal or a stop sign is. Forget about code for a moment. Watch some vids on the topic, then go back to coding out a solution. 

 

 

 

I can send you that dynamic allocator that I made if you want. Much of the boiler plate code are done for you so you can just get rid of my solution and write your own. 

[Gat Pelsinger]

@wasab

 

So basically, I need to learn the chunk system as I am not using it. But before learning it, I want to know if that even solves my problem. The situation is, I have many fragments of contiguous blocks of free memory and an allocation request arrives, but none of the contiguous blocks of free memory are enough to support this allocation request, and so the request is denied. Will using a chunk system let me use this fragmented memory? I don't really see how using chunks will get pass this issues, I mean sure, now fragmentation might be a bit controlled at the cost of memory usage efficiency, but when an allocation request demands more memory than any contiguous blocks of free memory can support, than what to do besides denying the request?

[wasab]

Quote

but none of the contiguous blocks of free memory are enough to support this allocation request, and so the request is denied.

search the implicit free list for free blocks that are either large enough or can be coalesced together into large enough blocks. if neither is available, ask the operating system for more memory then split it into chunks for coalesce/allocations as usual. return a NULL pointer if OS does not grant more memory.  

 

I suggest you watch the 2nd video carefully. this video pretty much has the solutions to all the problems you have. 

[Gat Pelsinger]

@wasab I can obviously ask for more memory but lets say my memory limit is controlled and I cannot allocate more than what is already allocated. Then there is no way to utilize the fragments?

[wasab]

1 hour ago, Gat Pelsinger said:

@wasab I can obviously ask for more memory but lets say my memory limit is controlled and I cannot allocate more than what is already allocated. Then there is no way to utilize the fragments?

Yeah, if program request 4 bytes and you only have one byte left, what's the point? Return a NULL pointer and set the errno code for out of memory.

 

Note, you should try to coalesced the fragmented free blocks and exhaust everything else before doing this. 

[Gat Pelsinger]

@wasab No you didn't get what I meant. Of course If I run out of memory than I have to exit, but I mentioned that I have no contiguous blocks of memory that can support the request BUT in total with all free memory fragments, I have enough memory to allocate for the request, its just that they are in fragments. So there is still no way to return some memory if I do not have any sufficient contiguous block of free memory and I cannot allocate more? If no, isn't this inefficient, that I have enough memory in total but I am still denying the request just because I have no system to return fragmented memory?

 

Edit - I know joining the free blocks is a thing, but lets I can't even do that. Don't bother commenting just to remind be about coalescing.

[wasab]

1 hour ago, Gat Pelsinger said:

snip

well, you can try moving memories around so all the free blocks are continuous but it is a very expensive operation which is a performance vs fragmentation trade-off. some dynamic memory allocator trades performance at the cost of more fragmentation. 

 

in reality, these memory addresses are all virtual. the real hardware rams and addresses they are mapped to might not be continuous themselves, that is handled by the operating system kernel. Also in real life, your operating system will be thrashing and page faulting long before it denies your program memory. the modern-day kernel is designed very well to always accommodate the process's request for more memory as best as it can. it would write a lot of it out to swap before it denies a memory request.

 

there are many techniques and alogrithms design to minimize such fragmentation btw. you can read up on the buddy system.

Buddy System - Memory allocation technique - GeeksforGeeks

[Gat Pelsinger]

@wasab So my last stop would be to learn these chunk systems and the buddy system you mentioned to overall reduce the fragmentation, but I want to ask one las thing is how does Windows itself map the memory? The memory physically may or may not be continuous, but it makes it appear to be contiguous. What algorithms does it use? HashMaps?

[wasab]

2 hours ago, Gat Pelsinger said:

@wasab So my last stop would be to learn these chunk systems and the buddy system you mentioned to overall reduce the fragmentation, but I want to ask one las thing is how does Windows itself map the memory? The memory physically may or may not be continuous, but it makes it appear to be contiguous. What algorithms does it use? HashMaps?

well, it uses a page table alongside a paging algorithm. modern-day processors all have a memory management unit built in to help with this. that is beyond the scope of a memory allocator. you just need to know buddy system is a general all-purpose memory allocation technique that can be used for an application's internal dynamic allocator. an operating system kernel might or might not use the same techniques when craving out and allocating memory for each individual process. there is trade off to buddy system and that is internal fragmentation. e.g. an application might request 3 bytes but you will give it 4 bytes because 4 is the next smallest fit in the power of 2. 1 byte is left unused in the block so internal fragmentation. 

 

as a system library that sits above the kernel, you dont have to worry about such things(how os allocates memory). you just request memory from the kernel and you will get memory, like magic. these addresses again are virtual. a ptr pointing to 0xfffff for example is likely NOT the 0xfffff in physical ram but it doesn't matter. OS will take care of the actual mapping. your dynamic allocator's jobs is to allocate the virtual memory and manage the virtual addresses that ptr points to, it doesn't have to care about the real physical address. It is kinda like how hypervisors that cloud servers run for virtualizing VMs if you think about it. OS is using virtualized hardware from the hypervisor and then itself virtualizes and abstracts away like say virtual hardware ram it gets from the hypervisor into virtual memory for its application processes which is kinda sick. computer is very fascinating under the hood.