We are going to implement malloc(), calloc(), realloc() and free(). It is a newbie degree article, so I will not spell out each detail. This memory allocator won't be fast and efficient, we is not going to adjust allocated memory to align to a page boundary, but we'll build a memory allocator that works. If you wish to have a look on the code in full, Memory Wave Program check out my github repo memalloc. Before we get into constructing the memory allocator, you must be conversant in the memory format of a program. A process runs inside its own virtual tackle area that’s distinct from the virtual address areas of other processes. As you possibly can see in the image, the stack and the heap develop in the opposite instructions. That is, brk factors to the end of the heap. Now if we need to allocate more memory within the heap, we have 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 can make use of sbrk() system call that lets us manipulate the program break. Calling sbrk(0) gives the present deal with of program break. Calling sbrk(x) with a constructive value increments brk by x bytes, in consequence allocating memory. Calling sbrk(-x) with a damaging worth decrements brk by x bytes, in consequence releasing memory. To be sincere, sbrk() just isn't our best buddy in 2015. There are higher alternate options like mmap() out there in the present day. It will possibly can only develop or shrink in LIFO order. However, the glibc implementation of malloc nonetheless makes use of sbrk() for allocating memory that’s not too huge in measurement. So, we are going to go forward with sbrk() for our simple memory allocator. The malloc(dimension) operate allocates measurement bytes of memory and returns a pointer to the allotted memory. Within the above code, we name sbrk() with the given dimension.

On success, dimension bytes are allocated on the heap. That was straightforward. Wasn’t it? The difficult part is freeing this memory. The free(ptr) operate frees the memory block pointed to by ptr, which must have been returned by a earlier call to malloc(), calloc() or realloc(). But to free a block of memory, the primary order of business is to know the dimensions of the memory block to be freed. In the present scheme of issues, this is not attainable as the size information just isn't stored anywhere. So, we will have to find a option to store the dimensions of an allocated block somewhere. Furthermore, we'd like to know that the heap memory the operating system has provided is contiguous. So we will only release memory which is at the tip of the heap. We can’t launch a block of memory within the center to the OS. Think about your heap to be one thing like a protracted loaf of bread which you can stretch and shrink at one end, but you will have to maintain it in a single piece.

To address this issue of not with the ability to release memory that’s not at the tip of the heap, we'll make a distinction between freeing memory and releasing memory. From now on, freeing a block of memory does not essentially imply we launch memory back to OS. It just signifies that we keep the block marked as free. This block marked as free may be reused on a later malloc() call. Since Memory Wave Program not at the top of the heap can’t be launched, that is the only manner forward for us. 2. Whether or not a block is free or not-free? To store this data, we'll add a header to every newly allocated memory block. The idea is simple. We use this memory house 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 utterly certain the blocks of memory allocated by our malloc is contiguous.

Imagine the calling program has a overseas sbrk(), or there’s a piece of memory mmap()ed in between our memory blocks. We also want a technique to traverse by our blocks for memory (why traverse? we'll get to know when we glance at the implementation of free()). So to maintain observe of the memory allotted by our malloc, we are going to put them in a linked list. Now, let’s wrap all the header struct in a union together with a stub variable of measurement sixteen bytes. This makes the header end up on a memory deal with aligned to sixteen bytes. Recall that the dimensions of a union is the bigger dimension of its members. So the union guarantees that the top of the header is memory aligned. The top of the header is the place the actual memory block begins and subsequently the memory offered to the caller by the allocator will probably be aligned to 16 bytes.