Free lists don't make sense, size-wise

[austanss]

I'm attempting to make a dynamic memory allocator for my kernel, yet I can't grasp the concept of free lists.

When three chunks are allocated, and the second one is freed, now you have a larger list.

How do you account for that?

[neon]

Hi,

When a block is free'd the allocator adds a header to it to store links and adds it to the list. The free list is implemented within the free blocks themselves. It doesn't release the block, it just adds it to the free list so it can be allocated again.

[nullplan]

The allocators I know store the free list structure elements inside the now free chunks. Therefore the free list doesn't take up any space, because that memory is free anyway.

[nexos]

In a free list, say you area A, area B, and area C. Each area is 4k in size. When you initialize the allocator, you will make the first 4 or 8 bytes of area A point to the base of area B, and the first 4 or 8 bytes of area B point to area C. Area C's first 4 or 8 bytes will contain NULL. To allocate an element, you will see that area is the first thing on the list. So, you will make your global list variable now point area B. If area A gets freed, then simply add it back to the list. Also, free lists are very fast (O(1)), and take up no space, but they allow for only one allocation unit size. To allow for multiple sizes while using free lists, you will have to use power of two allocator (very inefficient), an 257 byte allocation actually uses 512 bytes!), a buddy allocator (better, but not perfect), or a slab allocator (Solaris's allocator, probably the ideal heap allocator, but very complex). All of these, however, are based on free lists. Also, for physical memory allocators, a free list will work, but it will require you to map the page you allocate, which will take time. For PMMs, at an extra cost of memory, you can use a free stack, i.e., allocate some physical memory from your map for a free stack. I can explain the details if you wish

[austanss]

So, the free list nodes are stored in the free chunks. Got it. Also, when you say "fixed sized allocation", do you mean that you can only malloc a set amount of bytes, or that in order to malloc more, you need to allocate in chunks, e.g. if the caller wants to allocate 12 bytes, we allocate 2 chunks of 8 bytes, so 16 bytes?

And, when the link to the "next free node" is nullptr, do you request a new page when you are out of free chunks?

And, how do you merge free blocks?

[nexos]

A free list i used to manage one size of allocations. Merging free blocks and other things of that sort don't apply. If you are looking to make a truly general purpose allocator (no object pool based), then use a linked list or b-tree scheme. If you use free lists for a general allocator, you must have multiple free lists, one for every size you support. You can create those on demand (like a slab allocator) or use a scheme like a power of two allocator instead.

[austanss]

Well that's very discouraging from use of free lists. If I can't vary the size of allocations, I have to increase the size everytime I have a new, larger structure that needs allocation but isn't large enough to request individual pages.

[nexos]

Well that's very discouraging from use of free lists. If I can't vary the size of allocations, I have to increase the size everytime I have a new, larger structure that needs allocation but isn't large enough to request individual pages.

Actually, you don't, for example, a classic heap system(a power of two allocator) contains an array of free lists. The first first free list, contains a two byte allocation size, the second one has 4, the third one has 8, then 16, 32, 64, 128, 256, 512, until whatever your max size is (maybe, say, 4096?). To allocate, you round the requested size to the next power that is available. This does waste some memory, as a 257 byte request actually takes 512 bytes. The solution to this is the slab.