OSDev.org

There are couple ways I know of - bitmap, linked list, array.

Using a bitmap is the simplest approach. 1 bit in the bitmap is one memory block of physical memory. The address of the block depends on index of the bit set.
The allocation is fast as it's just search for 1 or n number of bits indicating a free block.
The problem I can see is that it can get quite big. I know that today's memory is cheap but 128 KiB is a bit big (4 GiB memory, 1 bit - 4096 B block).

In a linked list, a single entry can span multiple blocks. So instead of spending 160B to cover 20 blocks, I can just add one entry that is 8B and covers that 20 blocks.
One entry points to another. The allocation is slower since we need to jump around the memory.

Array is like the merge of the two previous approaches.
Fast access, single entry can cover multiple entries. The problem is in keeping it sorted and possibly making it resizable.

I've considered a tree, but it's rather too complex for just keeping track of allocated physical memory.

What's is a good approach on this?

128KB is 0.003% of 4GB - it's not really a large amount.

My memory manager uses 1 32 bit value for each frame, and it's perfectly fine. The reasoning behind is, that COW (copy-on-write) implementation is very simple, using reference counting. It takes 4 MiB to cover 4 GiB of memory. It is still just about 0.1% overhead. But in the long run, memory and time savings are absolutely worth it.

I personally use a bitmap. It is simple to write and fast with minimal overhead.

Came back to this topic after a break and yeah, maybe i am just a bit too paranoid.
This is rather from my Softwaredev that whenever i deal with data the size of couple kilobytes, a red light lights up in my head.