Memory Allocators a hundred and one - Write A Simple Memory Allocator
We will implement malloc(), calloc(), realloc() and free(). This can be a beginner level article, so I will not spell out each detail. This memory allocator won't be quick and efficient, we will not modify allotted memory to align to a page boundary, but we will build a memory allocator that works. If you want to have a look on the code in full, check out my github repo memalloc. Before we get into constructing the memory allocator, you have to be conversant in the memory format of a program. A process runs inside its own digital deal with area that’s distinct from the virtual deal with spaces of different processes. As you can see in the picture, the stack and the heap grow in the other directions. That is, brk points to the tip of the heap. Now if we need to allocate extra memory within the heap, we need to request the system to increment brk.
Similarly, to release memory we need to request the system to decrement brk. Assuming we run Linux (or a Unix-like system), we could make use of sbrk() system name that lets us manipulate the program break. Calling sbrk(0) gives the present address of program break. Calling sbrk(x) with a constructive worth increments brk by x bytes, as a result allocating memory. Calling sbrk(-x) with a unfavourable value decrements brk by x bytes, in consequence releasing memory. To be honest, sbrk() is not our greatest buddy in 2015. There are higher alternate options like mmap() out there right now. It might probably can only develop or shrink in LIFO order. Nonetheless, the glibc implementation of malloc still makes use of sbrk() for allocating memory that’s not too large in size. So, we will go ahead with sbrk() for our easy memory allocator. The malloc(dimension) perform allocates dimension bytes of memory and returns a pointer to the allocated Memory Wave Experience. In the above code, we call sbrk() with the given dimension.
On success, size bytes are allocated on the heap. That was easy. Wasn’t it? The tough part is freeing this memory. The free(ptr) function frees the memory block pointed to by ptr, which must have been returned by a previous name to malloc(), calloc() or realloc(). However to free a block of memory, the primary order of enterprise is to know the size of the memory block to be freed. In the present scheme of issues, this isn't doable as the size data is not stored wherever. So, we should discover a technique to retailer the size of an allotted block someplace. Moreover, we need to understand that the heap memory the operating system has supplied is contiguous. So we will solely launch memory which is at the top of the heap. We can’t launch a block of memory in the middle to the OS. Imagine your heap to be one thing like an extended loaf of bread that you can stretch and shrink at one end, however you have to keep it in a single piece.
To address this concern of not with the ability to launch memory that’s not at the end of the heap, we'll make a distinction between freeing memory and releasing memory. From now on, freeing a block of memory doesn't necessarily imply we release memory again to OS. It just signifies that we keep the block marked as free. This block marked as free could also be reused on a later malloc() call. Since memory not at the end of the heap can’t be released, that is the only means ahead for us. 2. Whether a block is free or not-free? To retailer this data, we will add a header to each newly allotted memory block. The concept is simple. We use this memory space returned by sbrk() to fit in both the header and the actual memory block. The header is internally managed, and is kept completely hidden from the calling program. We can’t be completely positive the blocks of memory allotted by our malloc is contiguous.
Think about the calling program has a international sbrk(), or there’s a piece of memory mmap()ed in between our memory blocks. We additionally want a approach to traverse by our blocks for memory (why traverse? we'll get to know when we look at the implementation of free()). So to maintain track of the memory allocated by our malloc, we will put them in a linked listing. Now, let’s wrap all the header struct in a union together with a stub variable of measurement 16 bytes. This makes the header end up on a memory tackle aligned to sixteen bytes. Recall that the scale of a union is the larger size of its members. So the union guarantees that the top of the header is memory aligned. The top of the header is where the actual memory block begins and subsequently the memory offered to the caller by the allocator will probably be aligned to 16 bytes.