c - 如何将位图中的位映射到伙伴分配器中的物理页？

Question

我使用位图创建了自己的伙伴分配器(用于管理内核的物理内存)，每个位对应于特定大小的页 block 。由于我映射了整个 4GiB 地址空间，逻辑上第 1 位将代表 4GiB block ，接下来的两位将代表 2GiB 的 block ，接下来的四位将代表 1GiB 的 block ，依此类推，直到我们达到 4KiB 的单个 block (页面大小)。获取位的子级就像记下位位置、bitN 和:
左节点 = 位N * 2
右节点 =bitN * 2 + 1
获取任何位的父级将按 bitN/2 计算。

从某种意义上说，整个位图看起来像:

bit number: [1] [2 3] [4 5 6 7] [8 9 10 11 12 13 14 15] [16 ... etc.]
holds block: 4G  2G    1G        512M                    256M  - 4KiB

我可以为每个相同大小的 block 映射唯一的物理地址，但由于采用此方案的方式，地址将重叠，这意味着可以返回相同的物理地址，例如，对于 4KiB block 或 16KiB block 。对于 2 的幂的位数尤其如此 - 位 1、2、4、8 等将始终指向最左边的物理 block ，即地址 0。位 3、6、12、24 等。也将始终指向从地址 2GiB 开始的同一 block ，但该 block 可以是任何(有效)大小!一个很好的输出示例是:

(assume address 0 is valid and isn't considered NULL for the sake of the example)
allocate(1) -- allocate 1 page, returns address 0x00000000. Valid usable range is 0-4095 (0x00000000 - 0x00001000).
allocate(524288) -- allocate 512k pages (2GiB), returns address 0x80000000. Valid usable range is 0x80000000-0xFFFFFFFF.
free((uint32_t *)0) -- free address 0. Page is reclaimed and merged with its free buddies.
allocate(16) -- allocate 16 pages, returns address 0x00000000! Same address but now with a bigger usable range of 0-65535!

正如您所看到的，通过此实现，相同的地址可以指向任何大小的 block ，我想知道如何获取此 block 大小，以便我可以索引位图并开始合并伙伴。但我花了几个小时试图找出如何进行反向映射，从位图中查找与地址相对应的位!我在分配任何数量的页面时都没有问题，并且获得了唯一的地址，但是一旦必须释放它们，我不知道如何索引回位图!有什么想法如何解决这个问题吗？

Answer 1

在我看来，每个 block 至少需要两位信息。一位用于跟踪 block 是否已被分割，另一位用于跟踪 block 是否已分配或空闲。一种可能的编码:

00 - page is part of a larger block
01 - block has been split
10 - free block
11 - allocated block