定长块池:一块一个 bit 的分配器

位图在手,这一篇咱们让概念篇里画的格子真正落地:一个能发块、能收块、能验住客身份的定长块池。

先写契约,再写实现

第一篇咱们吹过牛:接口约束写成编译器可检查的形式,实现少一个函数,static_assert 当场失败。现在轮到它出场。新建 include/ZerOS/kernel/mem/pool.hpp:

展开代码收起代码共 21 行

#pragma once
#include <concepts>
#include <expected>

namespace ZerOS::memory
{
    enum class MemoryAllocationError {
        Ok, OutOfMemory, Poisoned, NotOwned
    };

    template <typename Pool>
    concept MemoryPool = requires (Pool p, void* block) {
        // A Memory pool should be able to allocate and deallocate blocks
        {p.raw_allocate()} -> std::same_as<std::expected<void*, MemoryAllocationError>>;
        // And also can deallocate target
        {p.raw_deallocate(block)} -> std::same_as<MemoryAllocationError>;

        // for ISR Allocations, we should use try allocate
        {p.try_allocate()} -> std::same_as<void*>;
    };
}

概念真是一个契约。咱们说，一个内存池子，起码要具备如下的属性：

1. raw_allocate，可以分配出来指定的内存块，当然咱们不约束大小
2. raw_deallocate，有借有还嘛！
3. try_allocate，试试分配，ISR一类的不敢玩酣畅淋漓的拆expected。

欸，稍微提一下错误码的事情：

• OutOfMemory 是真的没格子了
• Poisoned 是检测到有人写过已释放的块,
• NotOwned 是您拿来归还的指针根本不是这池的——野指针、内部指针、double-free 全归它管。

为什么错误通道用 expected 不用 optional?下面池子的注释给了咱们两条理由:多数实现的 optional 要多付 8 字节;更重要的是错误分类不该在用户接口那层丢掉。

主角:两级位图定长块池

新建 include/ZerOS/kernel/mem/bitmap_allocate.hpp。整块贴下来太长,咱们顺着文件从上往下走,每段代码后面就地讲:

展开代码收起代码共 38 行

#pragma once
#include <cstddef>
#include <cstdint>
#include <cstring>
#include <expected>

#include "ZerOS/base/bitmap.hpp"
#include "ZerOS/kernel/mem/pool.hpp"

namespace ZerOS::memory {

#define ALL_ALIGNED alignas(alignof(std::max_align_t))

/**
 * @brief   This is a bitmap pool, allocating the stuff of buffer_
 *          Take a breathe, we use bitmap, which, we use a bit to shoow if we use a block
 *          Mentioned: One Block, One Stuff
 *
 * @tparam block_size
 * @tparam block_cnt
 * @tparam owns_poison_policy
 */
template <std::size_t block_size, std::size_t block_cnt, bool owns_poison_policy>
struct BitmapPool {
    static constexpr std::size_t BUFFER_SIZE = block_size * block_cnt;
    static constexpr std::size_t BITMAP_L2_SIZE = (block_cnt + 31) / 32;
    static constexpr std::size_t BLOCK_SIZE = block_size;
    // buffer_ is max-aligned (ALL_ALIGNED), so every block start is too;
    // Make<> static_asserts objects against this (see typeable.hpp).
    static constexpr std::size_t BLOCK_ALIGN = alignof(std::max_align_t);

    static_assert(BLOCK_SIZE % alignof(std::max_align_t) == 0,
                  "block size must keep every block max-aligned");
    // Why not optional
    // A. if we use optional, for most impls, it costs 8 bytes
    // B. for User Interfaces, we should never carry it

    constexpr BitmapPool() = default;

常量区这行 static_assert 把几何约束交给编译器:块尺寸必须是 max_align_t 的倍数,不然第二块开始就不对齐。BLOCK_ALIGN 把这条对齐要求存成常量,注释指的 typeable.hpp,就是下一篇 Make<> 拿它验对象的地方。ALL_ALIGNED 宏也定义在这,用它的 buffer_ 排在文件尾巴,咱们走到成员区再看它。

展开代码收起代码共 39 行

    // ------------------------------------------------------------------
    // Contract surface: these three together satisfy concept MemoryPool
    // ------------------------------------------------------------------
    std::expected<void*, MemoryAllocationError> raw_allocate() {
        const auto index = available_block_index();
        if (!IsAvailableIndex(index)) {
            return std::unexpected(MemoryAllocationError::OutOfMemory);
        }

        if constexpr (owns_poison_policy) {
            // Only blocks that HAVE been poisoned (freed once) can fail the check;
            // fresh .bss blocks are all-zero, which is not poison tampering.
            if (ever_poisoned_.test(index) && detected_poison(index)) {
                return std::unexpected(MemoryAllocationError::Poisoned);
            }
        }

        set_as_in_used(index);
        return fetch_target_block(index);
    }
    MemoryAllocationError raw_deallocate(void* block) {
        const auto index = index_of_given_ptr(block);
        if (!IsAvailableIndex(index)) {
            return MemoryAllocationError::NotOwned; // wild / interior / foreign pointer
        }

        if (!release_block(index)) {
            return MemoryAllocationError::NotOwned; // double free
        }

        poison_block(index); // no-op when poison policy is off
        return MemoryAllocationError::Ok;
    }

    // For ISR allocations: no expected, failure simply reported as nullptr
    void* try_allocate() {
        auto res = raw_allocate();
        return res ? *res : nullptr;
    }

公区就这三个函数,正好是上面 concept 点名的三件套。raw_allocate 的主干:找空块、验毒、占位、发指针;raw_deallocate 反着走:查指针身份、收块、毒化。中间那截 if constexpr (owns_poison_policy) 的验毒,眼下不用全看懂,下面 poison_block 一段是它的主场;两个 NotOwned 出口的判据也都在下面的私有函数里,咱们挨个下去。try_allocate 是给 ISR 的:中断里不敢拆 expected,失败折成 nullptr,一行转发完事。

  private:
    // we fetch the first available block, if not, return the
    // npos
    static constexpr std::size_t npos = static_cast<std::size_t>(-1);
    static constexpr bool IsAvailableIndex(std::size_t index) { return index != npos; }

    // bitmap using here, for 0, it is available, for 1, it is full
    std::size_t available_block_index() // fetch the available block recorded in the pool
    {
        // Boost the speed by using the l1 bitmap, fastly, we find the first zero in the l1 bitmap
        const auto word_index = bitmap_l1_.find_first_zero();
        if (word_index == decltype(bitmap_l1_)::npos) {
            return npos;
        }

        // OK, this is the case, find in this word
        return bitmap_l2_.first_zero_in_word(word_index);
    }

找空块的路径就两步:bitmap_l1_.find_first_zero() 定位第一个没满的 L2 字;first_zero_in_word 再进这个字,落到具体的 bit。两个位图各管一层:bitmap_l2_ 每块一位,记占用;bitmap_l1_ 每个字一位,记"这个字满了没"。上一篇咱们写过的"跳字+落位"两段式,原样上岗。找不到的时候返回 npos,这个哨兵值贯穿全文;raw_allocate 拿 IsAvailableIndex 一判,OutOfMemory 就是这么来的。

块数少的时候看不出便宜,块数一多好处才出来:整字整字地跳,搜索就压成了常数级。这个结构您应该已经眼熟了,商用 RTOS 的优先级就绪位图,就是这么找"最高优先级就绪任务"的;位图那篇头注释里写的 "allocators, schedulers" 也不是白写的,到调度器那一站它还会再出场一次。

展开代码收起代码共 29 行

    void set_as_in_used(std::size_t index) {
        bitmap_l2_.set(index);

        if (bitmap_l2_.word_full(index >> 5)) {
            bitmap_l1_.set(index >> 5); // ok, this is also full
        }

        used_++;
    }

    bool release_block(std::size_t index) // The index acquired by available_block_index
    {
        if (index >= block_cnt) {
            return false;
        }

        if (!bitmap_l2_.test(index)) {
            // you cant release a block that is not in use
            return false;
        }

        bitmap_l2_.clear(index);
        // l1 is the "word full" flag: freeing ANY block makes its word not-full.
        // Unconditional clear is idempotent and keeps the invariant honest.
        bitmap_l1_.clear(index >> 5);

        used_--;
        return true;
    }

占用位怎么维护,咱们看这一对函数。set_as_in_used 置上 L2 之后多看一眼:这个字满了没(word_full),满了就把 L1 的对应位也点上;release_block 反过来,清完 L2 无条件清 L1——注释里写明白了:任何一块被释放,这个字就回到"未满",无条件清是幂等的,不变量才立得住。double-free 的防线也在这个函数里:bitmap_l2_.test(index) 不过,说明这块根本没占着,false 递回去,上层翻成 NotOwned。

    constexpr void* fetch_target_block(std::size_t index) { return buffer_ + index * BLOCK_SIZE; }
    std::size_t index_of_given_ptr(void* ptr) {
        auto* p = static_cast<std::byte*>(ptr);
        if (p < buffer_ || p >= buffer_ + BUFFER_SIZE) {
            // Not in this scpoe
            return npos;
        }

        const auto off = static_cast<std::size_t>(p - buffer_);
        if (off % BLOCK_SIZE != 0) {
            // not aligned, All the target allocated should be aligned
            return npos;
        }

        return off / BLOCK_SIZE;
    }

归还指针的资格审查,就是 index_of_given_ptr 的两道检查:指针在不在池的地界里;在的话,偏移是不是块对齐。野指针、指向块中间的内部指针、别人池子的指针,都过不了这两关,连同上面 release_block 拦下的 double-free,统统 NotOwned。注意 p < buffer_ 这行:两个不相干对象比指针大小,严格讲是未指明行为,不过这是 host 侧代码、实践上人人这么写,真要较真是可以改成整数比较的——启动代码那边咱们守着"转整数再比"的纪律,两处对照,您自己掂量。

展开代码收起代码共 21 行

    // poisoned the target block
    static constexpr std::byte POISON_VALUE{0x67};
    void poison_block(std::size_t index) {
        if constexpr (owns_poison_policy) {
            auto* p = fetch_target_block(index);
            memset(p, std::to_integer<int>(POISON_VALUE), BLOCK_SIZE);
            ever_poisoned_.set(index); // from now on, this block is expected to stay poisoned
        }
    }
    bool detected_poison(std::size_t index) {
        if constexpr (!owns_poison_policy) {
            return false;
        }
        auto* p = static_cast<std::byte*>(fetch_target_block(index));
        for (std::size_t i = 0; i < BLOCK_SIZE; ++i) {
            if (p[i] != POISON_VALUE) {
                return true; // One write the session!
            }
        }
        return false;
    }

上面 raw_allocate 里那截 if constexpr,实现就在这一对函数,干的事不复杂。owns_poison_policy 开着的时候,块一归还,poison_block 就把整块填成 0x67,顺手在 ever_poisoned_ 里把这一位标上。这一位是干嘛用的,咱们往下看。

下次这个块再被分配出去之前,detected_poison 会先验一遍:整块是不是还是 0x67。只要有一位对不上,说明有人写过已释放的内存,Poisoned 打回,这个块不再发给您。

为什么位图池能这么干?空闲链就不行:链表要把 next 指针写进空闲块本身,块的内容天然是脏的,想验也无从验。位图把占用状态记在块外面,块释放之后干干净净,填了什么就是什么,被人动过一查便知。板上又没有 ASan,这套毒化就是咱们自助的 use-after-free 探测。

ever_poisoned_ 那个门控,是为了不冤枉好人。咱们想想看:从来没毒化过的新鲜 .bss 块本来就是全零,全零当然不等于满块 0x67,不挡一下,岂不是块块都要误报?所以只有毒化过的块才进这道检查。

    // Buffer Locations here, as it request all baasic
    ALL_ALIGNED std::byte buffer_[BUFFER_SIZE];
    base::Bitmap<block_cnt> bitmap_l2_;      // one bit per block: 1 = occupied
    base::Bitmap<BITMAP_L2_SIZE> bitmap_l1_; // one bit per l2 word: 1 = that word is full
    base::Bitmap<block_cnt> ever_poisoned_;  // 1 = block went through a poison-on-free cycle
    std::size_t used_ = 0; // block we have been used
};

#undef ALL_ALIGNED // OK, dont leek this out

// we should ensure that, BitmapPool is A Memory Pool
static_assert(MemoryPool<BitmapPool<64, 8, true>>);

} // namespace ZerOS::memory

成员区收尾,名字咱们全见过:buffer_ 挂着顶上的 ALL_ALIGNED,整块 buffer 按 max_align_t 对齐;再配合开头那条块尺寸的 static_assert,每一块的起点就都保得住对齐。三个位图成员各管一件事:L2 记占用,L1 记字满,ever_poisoned_ 记毒化史,used_ 数着在用的块数。#define 用完就 #undef,宏卫生,不往外漏。尾巴上那行 static_assert(MemoryPool<BitmapPool<64, 8, true>>) 咱们专门看一眼:池自己向 concept 证明自己,少实现一个接口,这行就把构建拦下来。

拿两万次操作招呼它

test/CMakeLists.txt 的清单添一行:

zeros_add_test(test_bitmap)
zeros_add_test(test_bitmap_pool)

然后 test/test_bitmap_pool.cpp,七个用例,全文:

展开代码收起代码共 170 行

#include <catch2/catch_test_macros.hpp>

#include <cstddef>
#include <cstdint>
#include <random>
#include <vector>

#include "ZerOS/kernel/mem/bitmap_allocate.hpp"

using ZerOS::memory::BitmapPool;
using ZerOS::memory::MemoryAllocationError;

TEST_CASE("distinct blocks, first-fit reuse, double free", "[pool]") {
    BitmapPool<64, 8, true> pool;

    auto a = pool.raw_allocate();
    auto b = pool.raw_allocate();
    REQUIRE(a.has_value());
    REQUIRE(b.has_value());
    CHECK(*a != *b); // different callers must never share a block

    REQUIRE(pool.raw_deallocate(*a) == MemoryAllocationError::Ok);
    auto c = pool.raw_allocate();
    REQUIRE(c.has_value());
    CHECK(*c == *a); // lowest freed index comes back first

    pool.raw_deallocate(*c);
    CHECK(pool.raw_deallocate(*c) == MemoryAllocationError::NotOwned);
}

TEST_CASE("wild and interior pointers are NotOwned", "[pool]") {
    BitmapPool<64, 8, true> pool;

    int dummy = 0; // a stack object living outside the pool
    CHECK(pool.raw_deallocate(&dummy) == MemoryAllocationError::NotOwned);

    auto taken = pool.raw_allocate();
    REQUIRE(taken.has_value());
    auto* interior = static_cast<std::byte*>(*taken) + 8;
    CHECK(pool.raw_deallocate(interior) == MemoryAllocationError::NotOwned);
}

TEST_CASE("100 blocks spanning 4 l2 words keep l1/l2 honest", "[pool][l1l2]") {
    // Regression for the classic trio: l2 typed with word-count bits,
    // l1 typed with L1_SIZE bits, release only clearing l1 when its
    // word became EMPTY (the old bug froze l1 bits set forever).
    BitmapPool<16, 100, false> pool;
    std::vector<void*> ps;

    for (std::size_t i = 0; i < 100; ++i) {
        auto r = pool.raw_allocate();
        REQUIRE(r.has_value());
        ps.push_back(*r);
    }
    CHECK_FALSE(pool.raw_allocate().has_value()); // exhausted

    pool.raw_deallocate(ps[33]); // the ONLY hole in the whole pool
    auto q = pool.raw_allocate();
    REQUIRE(q.has_value());
    CHECK(*q == ps[33]); // the hole must be found again through l1 -> l2
}

TEST_CASE("poison catches write-after-free", "[pool][poison]") {
    BitmapPool<64, 4, true> pool;

    auto v = pool.raw_allocate();
    REQUIRE(v.has_value());
    auto* p = static_cast<unsigned char*>(*v);
    pool.raw_deallocate(p); // poison-on-free fills the block

    p[3] ^= 0xFF;           // sneak write into a free block
    auto r = pool.raw_allocate();
    CHECK_FALSE(r.has_value());
    CHECK(r.error() == MemoryAllocationError::Poisoned);
}

TEST_CASE("a clean free reallocates without false poison", "[pool][poison]") {
    BitmapPool<64, 4, true> pool;

    auto v = pool.raw_allocate();
    REQUIRE(v.has_value());
    pool.raw_deallocate(*v); // nobody touched it since the free

    auto r = pool.raw_allocate();
    REQUIRE(r.has_value()); // ever_poisoned_ gates the check, must not misfire
    CHECK(*r == *v);
}

TEST_CASE("try_allocate reports exhaustion as nullptr", "[pool]") {
    BitmapPool<64, 2, false> pool;

    CHECK(pool.try_allocate() != nullptr);
    CHECK(pool.try_allocate() != nullptr);
    CHECK(pool.try_allocate() == nullptr); // ISR-safe surface, no expected<>
}

TEST_CASE("randomized torture: interleaved alloc/free keeps invariants", "[pool][fuzz]") {
    // Fixed seed: a failure must reproduce bit-for-bit on every machine.
    std::mt19937 rng{20260904u};

    constexpr std::size_t kBlocks = 64;
    BitmapPool<16, kBlocks, true> pool; // poison ON: exercises ever_poisoned_ gating too

    struct Live {
        void* p;
        std::uint64_t stamp;
    };
    std::vector<Live> live;
    live.reserve(kBlocks);

    std::size_t allocs = 0, frees = 0;
    constexpr std::size_t kOps = 20000;

    for (std::size_t op = 0; op < kOps; ++op) {
        // 55/45 bias towards alloc so the pool really saturates and drains;
        // forced alloc when empty keeps `live` indices well-defined.
        const bool want_alloc = live.empty() || (rng() % 100u) < 55u;

        if (want_alloc) {
            auto r = pool.raw_allocate();
            if (live.size() == kBlocks) {
                // holding every block => the pool must report exhaustion
                REQUIRE_FALSE(r.has_value());
                REQUIRE(r.error() == MemoryAllocationError::OutOfMemory);
                continue;
            }
            REQUIRE(r.has_value());

            // stamp the block: if the stamp is ever broken, two owners
            // (or a wild write) touched this block between alloc and free.
            const auto stamp = (static_cast<std::uint64_t>(op) << 32) ^ allocs;
            auto* w = static_cast<std::uint64_t*>(*r); // 16B blocks, max-aligned
            w[0] = stamp;
            w[1] = ~stamp;

            live.push_back({*r, stamp});
            ++allocs;
        } else {
            const auto idx = rng() % live.size();
            auto* w = static_cast<std::uint64_t*>(live[idx].p);
            REQUIRE(w[0] == live[idx].stamp); // still exclusively ours?
            REQUIRE(w[1] == ~live[idx].stamp);

            REQUIRE(pool.raw_deallocate(live[idx].p) == MemoryAllocationError::Ok);
            live.erase(live.begin() + static_cast<std::ptrdiff_t>(idx));
            ++frees;
        }
    }

    // drain: every survivor must still carry an intact stamp and free cleanly
    for (const auto& b : live) {
        auto* w = static_cast<std::uint64_t*>(b.p);
        REQUIRE(w[0] == b.stamp);
        REQUIRE(w[1] == ~b.stamp);
        REQUIRE(pool.raw_deallocate(b.p) == MemoryAllocationError::Ok);
    }
    live.clear();

    // a fully-drained pool must hand out all blocks again, then report full
    std::vector<void*> refill;
    for (std::size_t i = 0; i < kBlocks; ++i) {
        auto r = pool.raw_allocate();
        REQUIRE(r.has_value());
        refill.push_back(*r);
    }
    REQUIRE_FALSE(pool.raw_allocate().has_value());

    CHECK(allocs > 100); // guard against an accidentally idle test
    CHECK(frees > 100);
}

两个用例值得您写的时候慢下来。

您写 100 块那个用例时,注释值得逐行读:它记的是三个真实的历史 bug——l2 位图误用字数当位数、l1 误用 L1_SIZE 当位宽、释放时只有当字变空才清 l1,最后这个 bug 的后果是 l1 的位一旦置上就永远冻着,整个字再也找不回来。用例的做法是把 100 块全占满,只挖一个洞,再要求这个洞必须能被找到:洞要是找不到,只能是 l1 到 l2 的路断了。

fuzz 用例是这一篇的压舱石,值得您为它多停五分钟。种子固定 20260904:失败必须逐位可复现,换机器也一样;55/45 的分配偏置让池真的会打满再排干,而不是不痛不痒地摸两下;每个活块写进 stamp 和 ~stamp 两个值,释放前验一遍:stamp 破了,说明有两个主人或一次野写碰过这块。两万次操作下来,任何一个不变量崩了都会当场翻车。

验收

cmake --build build-host
./build-host/test/test_bitmap_pool

笔者本机的真实输出:

All tests passed (40295 assertions in 7 test cases)

四万条断言,大头全在 fuzz 里,您跑多少遍都一个数——种子是死的。全过即过。

池子能发 void* 了,但内核对象要的是类型。下一篇咱们写最后一层门面:Make<T>(pool, ... 让对象在池里出生,Destroy 让它体面入土,外加两道编译期防线和一个专门证明"防线存在"的负向测试。