How does malloc work?

Wikipedia tells us that malloc is a function that, given a specified number of bytes will allocate that number of bytes in memory and will typically return a pointer to the start of the address it allocated

System memory is usually managed by the kernel so if we'd like some memory we can ask it using a syscall. I know of two brk()/sbrk() and map()

brk and sbrk work by controlling the amount of memory allocated to the data segment of a process. The data segment just means the portion of memory where variables are stored.

brk takes a pointer extends the data segment to the address referenced by the pointer. This effectively increases the memory available to the process.

sbrk does something similar but it takes the size you want to increase the data segment by and adds that.

so we can implement malloc by calling sbrk with the size of the memory we want.

Pretty simple. So what about mmap?

mmap works a bit differently. mmap is called that because it does something called memory mapping.

Memory mapping is the act of using virtual memory to represent a resource.

Say you have a very large file that's about say 10gb and you'd like to write to it.

You could read/write directly to the file on disk but that could be a bit slow. If you could some how copy a part of that file into memory. read / write from that bit and write only your changes to disk, you'd be able to work on it a bit faster.

Memory mapping lets you do exactly that. You mark a portion of memory to represent a resource or part of a resource and then you work with it as the resource. That bit of memory "maps" to the resource. That's why it's called memory mapping.

Now that we know what memory mapping is how does that let us malloc? well mmap kind of does the same thing sbrk does. It makes some portion of memory available and returns a pointer to it.

So we can implement malloc like this

If you'd like to read a bit more about this please read here https://danluu.com/malloc-tutorial/

Now let's talk about free(). Free at first looks like it should release memory from the process by either reducing the size of the data segment or unmapping the mapped memory

but you may not want to do that. since asking the OS for memory is relatively expensive you may want to hold on to the memory you have already requested for future malloc calls.

So when free() is called what it does is mark the memory as available so that when malloc is called that memory the program is already holding can be used up first before making more requests to the OS.

this is why you can still read from a pointer after calling free() on it. The memory address it refers to is marked as available to be overwritten but it isn't cleared just yet. So if you deref the pointer you'll get the same value assuming it hasn't been overwritten.

Production implementations of malloc will probably use both sys calls. using sbrk for small memory allocations and mmap for large ones. As well as a data structure to keep track of already requested memory.