What kind of data structure is this?

[deadmutex]

While creating a page allocator for my kernel, I came up with an unfamiliar data structure for keeping track of used/free pages. It's an extension of the bitmap allocator. Instead of just using one bitmap where each bit corresponds to the used/free status of a single page, I use 'tiers' of bitmaps. I group the pages into chunks of 32. Each dword in a bitmap is called a chunk. Each bit in bitmap N+1 corresponds to a chunk in bitmap N and it indicates whether that chunk contains at least one free entry or none. When all bits in a chunk are set to used, then the bit corresponding to that chunk is also set to used.

If I have 2 GiB of physical memory, I'd have 524,288 4-KiB pages. If each page is represented by a bit, then:

Tier 3 bitmap: 16 entries, 1 chunk, 4 B in size (2 B are unused)
Tier 2 bitmap: 512 entries, 16 chunks, 64 B in size
Tier 1 bitmap: 16,384 entries, 512 chunks, 2 KiB in size
Tier 0 bitmap: 524,288 entries, 16,384 chunks, 64 KiB in size

Searching for a free entry is done by a binary search on the chunk. Let 0 represent 'free' and 1 represent 'used.' If a chunk is equal to 0xFFFFFFFF, then all entries are used. If not, then at least one entry is free. Split the chunk in two. If the left half equals 0xFFFF, then the free entry must be in the right half. Otherwise, there's a free entry in the left half. Select the half with the free entry and repeat the splitting and selecting process until you're left with the free bit.

I'm not exactly sure what kind of data structure this is. It sorta looks like a B-tree, but with bits. It also looks like the structure used for the buddy allocator. Is there an actual name for this?

[dozniak]

This?

[deadmutex]

This?

I think that might be it, except in my case I seem to also use a bitmap index for multiple bitmap indices, and a bitmap index for bitmap indices for bitmap indices, and so on.