A buddy allocator test

gistfile1.txt

// testing functions
static void log_freelists();
static bool validate_freelists();
static void get_freelist_lens(size_t lens[BLOCK_SIZES]);

// test_kalloc
//    Run unit tests on the kalloc system.
void test_kalloc() {
    assert(validate_freelists());

    auto pre = static_cast<size_t*>(kalloc(BLOCK_SIZES * sizeof(size_t)));
    auto post = static_cast<size_t*>(kalloc(BLOCK_SIZES * sizeof(size_t)));
    assert(pre != nullptr && post != nullptr);

    // initial measurement
    get_freelist_lens(pre);

    // do a bunch of allocations
    const size_t n_allocs = 200;
    auto allocations = static_cast<void**>(kalloc(n_allocs * sizeof(void*)));
    assert(allocations != nullptr);
    for (size_t i = 0; i < n_allocs; ++i) {
        allocations[i] = kalloc((i + 1) * 100);
        assert(allocations[i] != nullptr);
    }

    assert(validate_freelists());

    // free everything
    for (size_t i = 0; i < n_allocs; ++i) {
        kfree(allocations[(i % 2) ? (i/2) : (n_allocs - 1 - i/2)]);
    }
    kfree(allocations);

    assert(validate_freelists());

    // final measurement
    get_freelist_lens(post);

    // make sure freelist lengths are the same
    for (size_t i = 0; i < BLOCK_SIZES; ++i) {
        assert(pre[i] == post[i]);
    }

    // cleanup
    kfree(pre);
    kfree(post);
}

static void log_freelists() {
    for (size_t i = 0; i < BLOCK_SIZES; ++i) {
        log_printf("%d:\t", index2size(i));
        for (auto cur = freelists[i].front();
             cur != nullptr;
             cur = freelists[i].next(cur)) {
            log_printf("%p, ", cur);
        }
        log_printf("\n");
    }
}

static bool validate_freelists() {
    for (size_t i = 0; i < BLOCK_SIZES; ++i) {
        // if (!freelists[i].validate()) {
        //     log_printf("freelist[%d]: invalid list structure\n", i);
        //     return false;
        // }
        size_t item = 0;
        for (auto cur = freelists[i].front();
             cur != nullptr;
             cur = freelists[i].next(cur)) {
            auto entry = get_pageinfo(reinterpret_cast<uint8_t*>(cur));
            if (entry->refcount != 0) {
                log_printf("freelist[%d]: item %d refcount is %d\n",
                           i, item, entry->refcount);
                return false;
            }
            if (entry->size != index2size(i)) {
                log_printf("freelist[%d]: item %d size is %d (not %d)\n",
                           i, item, entry->size, index2size(i));
                return false;
            }
            ++item;
        }
    }
    return true;
}

static void get_freelist_lens(size_t lens[BLOCK_SIZES]) {
    for (size_t i = 0; i < BLOCK_SIZES; ++i) {
        lens[i] = 0;
        for (auto cur = freelists[i].front();
             cur != nullptr;
             cur = freelists[i].next(cur)) {
            ++lens[i];
        }
    }
}



// add to k-list.hh
template <typename T, list_links (T::* member)>
bool list<T, member>::validate() {
    if (head_.next_ == nullptr) {
        log_printf("list %p: head next field is nullptr\n", this);
        return false;
    }
    if (head_.prev_ == nullptr) {
        log_printf("list %p: head prev field is nullptr\n", this);
        return false;
    }
    list_links* last = &head_;
    for (auto cur = front(); cur; cur = next(cur)) {
        if ((cur->*member).next_ == nullptr) {
            log_printf("list %p: %p next field is nullptr\n", this, cur);
            return false;
        }
        if ((cur->*member).prev_ == nullptr) {
            log_printf("list %p: %p prev field is nullptr\n", this, cur);
            return false;
        }
        if ((cur->*member).prev_ != last) {
            log_printf("list %p: %p prev field (%p) should be (%p)\n",
                       this, cur, (cur->*member).prev_, last);
            return false;
        }
        if (&(cur->*member) != last->next_) {
            log_printf("list %p: %p next field (%p) should be (%p)\n",
                       this, last, last->next_, cur);
            return false;
        }
        last = &(cur->*member);
    }
    if (last->next_ != &head_) {
        log_printf("list %p: last next field (%p) should be (%p)\n",
                   this, last->next_, &head_);
        return false;
    }
    if (head_.prev_ != last) {
        log_printf("list %p: head prev field (%p) should be (%p)\n",
                   this, head_.prev_, last);
        return false;
    }
    return true;
}