DragonOS/kernel/mm/slab.c

#include "slab.h"

/**
 * @brief 创建一个内存池
 *
 * @param size 内存池容量大小
 * @param constructor 构造函数
 * @param destructor 析构函数
 * @param arg 参数
 * @return struct slab* 构建好的内存池对象
 */
struct slab *slab_create(ul size, void *(*constructor)(void *vaddr, ul arg), void *(*destructor)(void *vaddr, ul arg), ul arg)
{
    struct slab *slab_pool = (struct slab *)kmalloc(sizeof(struct slab), 0);

    // BUG
    if (slab_pool == NULL)
    {
        kBUG("slab_create()->kmalloc()->slab == NULL");
        return NULL;
    }

    memset(slab_pool, 0, sizeof(struct slab));

    slab_pool->size = SIZEOF_LONG_ALIGN(size);
    slab_pool->count_total_using = 0;
    slab_pool->count_total_free = 0;
    // 直接分配cache_pool结构体，避免每次访问都要检测是否为NULL，提升效率
    slab_pool->cache_pool = (struct slab_obj *)kmalloc(sizeof(struct slab_obj), 0);

    // BUG
    if (slab_pool->cache_pool == NULL)
    {
        kBUG("slab_create()->kmalloc()->slab->cache_pool == NULL");
        kfree(slab_pool);
        return NULL;
    }
    memset(slab_pool->cache_pool, 0, sizeof(struct slab_obj));

    // dma内存池设置为空
    slab_pool->cache_dma_pool = NULL;

    // 设置构造及析构函数
    slab_pool->constructor = constructor;
    slab_pool->destructor = destructor;

    list_init(&slab_pool->cache_pool->list);

    // 分配属于内存池的内存页
    slab_pool->cache_pool->page = alloc_pages(ZONE_NORMAL, 1, PAGE_KERNEL);

    // BUG
    if (slab_pool->cache_pool->page == NULL)
    {
        kBUG("slab_create()->kmalloc()->slab->cache_pool == NULL");
        kfree(slab_pool->cache_pool);
        kfree(slab_pool);
        return NULL;
    }

    // page_init(slab_pool->cache_pool->page, PAGE_KERNEL);

    slab_pool->cache_pool->count_using = 0;
    slab_pool->cache_pool->count_free = PAGE_2M_SIZE / slab_pool->size;

    slab_pool->count_total_free = slab_pool->cache_pool->count_free;

    slab_pool->cache_pool->vaddr = phys_2_virt(slab_pool->cache_pool->page->addr_phys);

    // bitmap有多少有效位
    slab_pool->cache_pool->bmp_count = slab_pool->cache_pool->count_free;

    // 计算位图所占的空间 占用多少byte（按unsigned long大小的上边缘对齐）
    slab_pool->cache_pool->bmp_len = ((slab_pool->cache_pool->bmp_count + sizeof(ul) * 8 - 1) >> 6) << 3;
    // 初始化位图
    slab_pool->cache_pool->bmp = (ul *)kmalloc(slab_pool->cache_pool->bmp_len, 0);

    // BUG
    if (slab_pool->cache_pool->bmp == NULL)
    {
        kBUG("slab_create()->kmalloc()->slab->cache_pool == NULL");
        free_pages(slab_pool->cache_pool->page, 1);
        kfree(slab_pool->cache_pool);
        kfree(slab_pool);
        return NULL;
    }
    // 将位图清空
    memset(slab_pool->cache_pool->bmp, 0, slab_pool->cache_pool->bmp_len);

    return slab_pool;
}

/**
 * @brief 销毁内存池对象
 * 只有当slab对象是空的时候才能销毁
 * @param slab_pool 要销毁的内存池对象
 * @return ul
 *
 */
ul slab_destroy(struct slab *slab_pool)
{
    struct slab_obj *slab_obj_ptr = slab_pool->cache_pool;
    if (slab_pool->count_total_using)
    {
        kBUG("slab_cache->count_total_using != 0");
        return ESLAB_NOTNULL;
    }

    struct slab_obj *tmp_slab_obj = NULL;
    while (!list_empty(&slab_obj_ptr->list))
    {
        tmp_slab_obj = slab_obj_ptr;
        // 获取下一个slab_obj的起始地址
        slab_obj_ptr = container_of(list_next(&slab_obj_ptr->list), struct slab_obj, list);

        list_del(&tmp_slab_obj->list);

        kfree(tmp_slab_obj->bmp);

        page_clean(tmp_slab_obj->page);

        free_pages(tmp_slab_obj->page, 1);

        kfree(tmp_slab_obj);
    }

    kfree(slab_obj_ptr->bmp);
    page_clean(slab_obj_ptr->page);
    free_pages(slab_obj_ptr->page, 1);
    kfree(slab_obj_ptr);
    kfree(slab_pool);

    return 0;
}

/**
 * @brief 分配SLAB内存池中的内存对象
 *
 * @param slab_pool slab内存池
 * @param arg 传递给内存对象构造函数的参数
 * @return void* 内存空间的虚拟地址
 */
void *slab_malloc(struct slab *slab_pool, ul arg)
{
    struct slab_obj *slab_obj_ptr = slab_pool->cache_pool;
    struct slab_obj *tmp_slab_obj = NULL;

    // slab内存池中已经没有空闲的内存对象，进行扩容
    if (slab_pool->count_total_free == 0)
    {
        tmp_slab_obj = (struct slab_obj *)kmalloc(sizeof(struct slab_obj), 0);

        // BUG
        if (tmp_slab_obj == NULL)
        {
            kBUG("slab_malloc()->kmalloc()->slab->tmp_slab_obj == NULL");
            return NULL;
        }

        memset(tmp_slab_obj, 0, sizeof(struct slab_obj));
        list_init(&tmp_slab_obj->list);

        tmp_slab_obj->page = alloc_pages(ZONE_NORMAL, 1, PAGE_KERNEL);

        // BUG
        if (tmp_slab_obj->page == NULL)
        {
            kBUG("slab_malloc()->kmalloc()=>tmp_slab_obj->page == NULL");
            kfree(tmp_slab_obj);
            return NULL;
        }

        tmp_slab_obj->count_using = 0;
        tmp_slab_obj->count_free = PAGE_2M_SIZE / slab_pool->size;
        tmp_slab_obj->vaddr = phys_2_virt(tmp_slab_obj->page->addr_phys);
        tmp_slab_obj->bmp_count = tmp_slab_obj->count_free;
        // 计算位图所占的空间 占用多少byte（按unsigned long大小的上边缘对齐）
        tmp_slab_obj->bmp_len = ((tmp_slab_obj->bmp_count + sizeof(ul) * 8 - 1) >> 6) << 3;
        tmp_slab_obj->bmp = (ul *)kmalloc(tmp_slab_obj->bmp_len, 0);

        // BUG
        if (tmp_slab_obj->bmp == NULL)
        {
            kBUG("slab_malloc()->kmalloc()=>tmp_slab_obj->bmp == NULL");
            free_pages(tmp_slab_obj->page, 1);
            kfree(tmp_slab_obj);
            return NULL;
        }

        memset(tmp_slab_obj->bmp, 0, tmp_slab_obj->bmp_len);

        list_add(&slab_pool->cache_pool->list, tmp_slab_obj);

        slab_pool->count_total_free += tmp_slab_obj->count_free;

        slab_obj_ptr = tmp_slab_obj;
    }

    // 扩容完毕或无需扩容，开始分配内存对象
    int tmp_md;
    do
    {
        if (slab_obj_ptr->count_free == 0)
        {
            slab_obj_ptr = container_of(list_next(&slab_obj_ptr->list), struct slab_obj, list);
            continue;
        }

        for (int i = 0; i < slab_obj_ptr->bmp_count; ++i)
        {
            // 当前bmp对应的内存对象都已经被分配
            if (*(slab_obj_ptr->bmp + (i >> 6)) == 0xffffffffffffffffUL)
            {
                i += 63;
                continue;
            }

            // 第i个内存对象是空闲的
            tmp_md = i % 64;
            if ((*(slab_obj_ptr->bmp + (i >> 6)) & (1UL << tmp_md)) == 0)
            {
                // 置位bmp
                *(slab_obj_ptr->bmp + (i >> 6)) |= (1UL << tmp_md);

                // 更新当前slab对象的计数器
                ++(slab_obj_ptr->count_using);
                --(slab_obj_ptr->count_free);
                // 更新slab内存池的计数器
                ++(slab_pool->count_total_using);
                --(slab_pool->count_total_free);

                if (slab_pool->constructor != NULL)
                {
                    // 返回内存对象指针（要求构造函数返回内存对象指针）
                    return slab_pool->constructor((char *)slab_obj_ptr->vaddr + slab_pool->size * i, arg);
                }
                // 返回内存对象指针
                else
                    return (void *)((char *)slab_obj_ptr->vaddr + slab_pool->size * i);
            }
        }

    } while (slab_obj_ptr != slab_pool->cache_pool);

    // should not be here

    kBUG("slab_malloc() ERROR: can't malloc");

    // 释放内存
    if (tmp_slab_obj != NULL)
    {
        list_del(&tmp_slab_obj->list);
        kfree(tmp_slab_obj->bmp);
        page_clean(tmp_slab_obj->page);
        free_pages(tmp_slab_obj->page, 1);
        kfree(tmp_slab_obj);
    }
    return NULL;
}

/**
 * @brief 回收slab内存池中的对象
 *
 * @param slab_pool 对应的内存池
 * @param addr 内存对象的虚拟地址
 * @param arg 传递给虚构函数的参数
 * @return ul
 */
ul slab_free(struct slab *slab_pool, void *addr, ul arg)
{
    struct slab_obj *slab_obj_ptr = slab_pool->cache_pool;

    do
    {
        // 虚拟地址不在当前内存池对象的管理范围内
        if (!(slab_obj_ptr->vaddr <= addr && addr <= (slab_obj_ptr->vaddr + PAGE_2M_SIZE)))
        {
            slab_obj_ptr = container_of(list_next(&slab_obj_ptr->list), struct slab_obj, list);
            continue;
        }

        // 计算出给定内存对象是第几个
        int index = (addr - slab_obj_ptr->vaddr) / slab_pool->size;

        // 复位位图中对应的位
        *(slab_obj_ptr->bmp + (index >> 6)) ^= (1UL << index % 64);

        ++(slab_obj_ptr->count_free);
        --(slab_obj_ptr->count_using);

        ++(slab_pool->count_total_free);
        --(slab_pool->count_total_using);

        // 有对应的析构函数，调用析构函数
        if (slab_pool->destructor != NULL)
            slab_pool->destructor((char *)slab_obj_ptr->vaddr + slab_pool->size * index, arg);

        // 当前内存对象池的正在使用的内存对象为0，且内存池的空闲对象大于当前对象池的2倍，则销毁当前对象池，以减轻系统内存压力
        if ((slab_obj_ptr->count_using == 0) && ((slab_pool->count_total_free >> 1) >= slab_obj_ptr->count_free))
        {
            // 防止删除了slab_pool的cache_pool入口
            if (slab_pool->cache_pool == slab_obj_ptr)
                slab_pool->cache_pool = container_of(list_next(&slab_obj_ptr->list), struct slab_obj, list);

            list_del(&slab_obj_ptr->list);
            slab_pool->count_total_free -= slab_obj_ptr->count_free;

            kfree(slab_obj_ptr->bmp);
            page_clean(slab_obj_ptr->page);
            free_pages(slab_obj_ptr->page, 1);
            kfree(slab_obj_ptr);
        }

        return 0;
    } while (slab_obj_ptr != slab_pool->cache_pool);

    kwarn("slab_free(): address not in current slab");
    return ENOT_IN_SLAB;
}

/**
 * @brief 初始化内存池组
 * 在初始化通用内存管理单元期间，尚无内存空间分配函数，需要我们手动为SLAB内存池指定存储空间
 * @return ul
 */
ul slab_init()
{
    // 将slab的内存池空间放置在mms的后方
    ul tmp_addr = memory_management_struct.end_of_struct;

    for (int i = 0; i < 16; ++i)
    {
        // 将slab内存池对象的空间放置在mms的后面，并且预留4个unsigned long 的空间以防止内存越界
        kmalloc_cache_group[i].cache_pool = (struct slab_obj *)memory_management_struct.end_of_struct;
        memory_management_struct.end_of_struct += sizeof(struct slab_obj) + (sizeof(ul) << 2);

        list_init(&(kmalloc_cache_group[i].cache_pool->list));

        // 初始化内存池对象
        kmalloc_cache_group[i].cache_pool->count_using = 0;
        kmalloc_cache_group[i].cache_pool->count_free = PAGE_2M_SIZE / kmalloc_cache_group[i].size;
        kmalloc_cache_group[i].cache_pool->bmp_len = (((kmalloc_cache_group[i].cache_pool->count_free + sizeof(ul) * 8 - 1) >> 6) << 3);
        kmalloc_cache_group[i].cache_pool->bmp_count = kmalloc_cache_group[i].cache_pool->count_free;

        // 在slab对象后方放置bmp
        kmalloc_cache_group[i].cache_pool->bmp = (ul *)memory_management_struct.end_of_struct;

        // bmp后方预留4个unsigned long的空间防止内存越界,且按照8byte进行对齐
        memory_management_struct.end_of_struct += kmalloc_cache_group[i].cache_pool->bmp_len + ((sizeof(ul) << 2) & (~sizeof(ul) - 1));

        // @todo：此处可优化，直接把所有位设置为0，然后再对部分不存在对应的内存对象的位设置为1
        memset(kmalloc_cache_group[i].cache_pool->bmp, 0xff, kmalloc_cache_group[i].cache_pool->bmp_len);
        for (int j = 0; j < kmalloc_cache_group[i].cache_pool->bmp_count; ++j)
            *(kmalloc_cache_group[i].cache_pool->bmp + (j >> 6)) ^= 1UL << (j % 64);

        kmalloc_cache_group[i].count_total_using = 0;
        kmalloc_cache_group[i].count_total_free = kmalloc_cache_group[i].cache_pool->count_free;
    }

    struct Page *page = NULL;

    // 将上面初始化内存池组时，所占用的内存页进行初始化
    ul tmp_page_mms_end = virt_2_phys(memory_management_struct.end_of_struct >> PAGE_2M_SHIFT);
    for (int i = PAGE_2M_ALIGN(virt_2_phys(tmp_addr)); i < tmp_page_mms_end; ++i)
    {
        page = memory_management_struct.pages_struct + i;

        // 下面注释掉的这部分工作貌似在page_init()里面已经做了
        // 在mms的bmp中，置位对应的位
        //*(memory_management_struct.bmp + ((page->addr_phys>>PAGE_2M_SHIFT)>>6)) |= 1UL<<((page->addr_phys >> PAGE_2M_SHIFT)%64);

        //++(page->zone->count_pages_using);
        //--(page->zone->count_pages_free);

        page_init(page, PAGE_KERNEL_INIT | PAGE_KERNEL | PAGE_PGT_MAPPED);
    }

    printk_color(ORANGE, BLACK, "2.memory_management_struct.bmp:%#018lx\tzone_struct->count_pages_using:%d\tzone_struct->count_pages_free:%d\n", *memory_management_struct.bmp, memory_management_struct.zones_struct->count_pages_using, memory_management_struct.zones_struct->count_pages_free);

    // 为slab内存池对象分配内存空间
    ul *virt = NULL;
    for (int i = 0; i < 16; ++i)
    {
        // 获取一个新的空页并添加到空页表，然后返回其虚拟地址
        virt = (ul *)(PAGE_2M_ALIGN(memory_management_struct.end_of_struct + PAGE_2M_SIZE * i));
        page = Virt_To_2M_Page(virt);

        page_init(page, PAGE_PGT_MAPPED | PAGE_KERNEL | PAGE_KERNEL_INIT);

        kmalloc_cache_group[i].cache_pool->page = page;
        kmalloc_cache_group[i].cache_pool->vaddr = virt;
    }
    printk_color(ORANGE, BLACK, "3.memory_management_struct.bmp:%#018lx\tzone_struct->count_pages_using:%d\tzone_struct->count_pages_free:%d\n", *memory_management_struct.bmp, memory_management_struct.zones_struct->count_pages_using, memory_management_struct.zones_struct->count_pages_free);

    return 0;
}

/**
 * @brief 在kmalloc中创建slab_obj的函数（与slab_malloc()中的类似)
 *
 * @param size
 * @return struct slab_obj* 创建好的slab_obj
 */

struct slab_obj *kmalloc_create_slab_obj(ul size)
{
    struct Page *page = alloc_pages(ZONE_NORMAL, 1, 0);

    // BUG
    if (page == NULL)
    {
        kBUG("kmalloc_create()->alloc_pages()=>page == NULL");
        return NULL;
    }

    page_init(page, PAGE_KERNEL);

    ul *vaddr = NULL;
    ul struct_size = 0;
    struct slab_obj *slab_obj_ptr;

    // 根据size大小，选择不同的分支来处理
    // 之所以选择512byte为分界点，是因为，此时bmp大小刚好为512byte。显而易见，选择过小的话会导致kmalloc函数与当前函数反复互相调用，最终导致栈溢出
    switch (size)
    {
    // ============ 对于size<=512byte的内存池对象，将slab_obj结构体和bmp放置在物理页的内部 ========
    // 由于这些对象的特征是，bmp占的空间大，而内存块的空间小，这样做的目的是避免再去申请一块内存来存储bmp，减少浪费。
    case 32:
    case 64:
    case 128:
    case 256:
    case 512:
        vaddr = phys_2_virt(page->addr_phys);
        // slab_obj结构体的大小 （本身的大小+bmp的大小）
        struct_size = sizeof(struct slab_obj) + PAGE_2M_SIZE / size / 8;
        // 将slab_obj放置到物理页的末尾
        slab_obj_ptr = (struct slab_obj *)((unsigned char *)vaddr + PAGE_2M_SIZE - struct_size);
        slab_obj_ptr->bmp = (ul *)slab_obj_ptr + sizeof(struct slab_obj);

        slab_obj_ptr->count_free = (PAGE_2M_SIZE - struct_size) / size;
        slab_obj_ptr->count_using = 0;
        slab_obj_ptr->bmp_count = slab_obj_ptr->count_free;
        slab_obj_ptr->vaddr = vaddr;
        slab_obj_ptr->page = page;

        list_init(&slab_obj_ptr->list);

        slab_obj_ptr->bmp_len = ((slab_obj_ptr->bmp_count + sizeof(ul) * 8 - 1) >> 6) << 3;

        // @todo：此处可优化，直接把所有位设置为0，然后再对部分不存在对应的内存对象的位设置为1
        memset(slab_obj_ptr->bmp, 0xff, slab_obj_ptr->bmp_len);

        for (int i = 0; i < slab_obj_ptr->bmp_count; ++i)
            *(slab_obj_ptr->bmp + (i >> 6)) ^= 1UL << (i % 64);

        break;
    // ================= 较大的size时，slab_obj和bmp不再放置于当前物理页内部 ============
    // 因为在这种情况下，bmp很短，继续放置在当前物理页内部则会造成可分配的对象少，加剧了内存空间的浪费
    case 1024: // 1KB
    case 2048:
    case 4096: // 4KB
    case 8192:
    case 16384:
    case 32768:
    case 65536:
    case 131072: // 128KB
    case 262144:
    case 524288:
    case 1048576: // 1MB
        slab_obj_ptr = (struct Slab *)kmalloc(sizeof(struct slab_obj), 0);

        slab_obj_ptr->count_free = PAGE_2M_SIZE / size;
        slab_obj_ptr->count_using = 0;
        slab_obj_ptr->bmp_count = slab_obj_ptr->count_free;

        slab_obj_ptr->bmp_len = ((slab_obj_ptr->bmp_count + sizeof(ul) * 8 - 1) >> 6) << 3;

        slab_obj_ptr->bmp = (ul *)kmalloc(slab_obj_ptr->bmp_len, 0);

        // @todo：此处可优化，直接把所有位设置为0，然后再对部分不存在对应的内存对象的位设置为1
        memset(slab_obj_ptr->bmp, 0xff, slab_obj_ptr->bmp_len);
        for (int i = 0; i < slab_obj_ptr->bmp_count; ++i)
            *(slab_obj_ptr->bmp + (i >> 6)) ^= 1UL << (i % 64);

        slab_obj_ptr->vaddr = phys_2_virt(page->addr_phys);
        slab_obj_ptr->page = page;
        list_init(&slab_obj_ptr->list);
        break;
    // size 错误
    default:
        kerror("kamlloc_create(): Wrong size%d\n", size);
        free_pages(page, 1);
        return NULL;
        break;
    }

    return slab_obj_ptr;
}

/**
 * @brief 通用内存分配函数
 *
 * @param size 要分配的内存大小
 * @param flags 内存的flag
 * @return void* 内核内存虚拟地址
 */
void *kmalloc(unsigned long size, unsigned long flags)
{
    if (size > 1048576)
    {
        kwarn("kmalloc(): Can't alloc such memory: %ld bytes, because it is too large.", size);
        return NULL;
    }
    int index;
    for (int i = 0; i < 16; ++i)
        if (kmalloc_cache_group[i].size >= size)
        {
            index = i;
            break;
        }

    struct slab_obj *slab_obj_ptr = kmalloc_cache_group[index].cache_pool;

    // 内存池没有可用的内存对象，需要进行扩容
    if (kmalloc_cache_group[index].count_total_free == 0)
    {
        // 创建slab_obj
        slab_obj_ptr = kmalloc_create_slab_obj(kmalloc_cache_group[index].size);

        // BUG
        if (slab_obj_ptr == NULL)
        {
            kBUG("kmalloc()->kmalloc_create_slab_obj()=>slab == NULL");
            return NULL;
        }

        kmalloc_cache_group[index].count_total_free += slab_obj_ptr->count_free;
        list_add(&kmalloc_cache_group[index].cache_pool->list, &slab_obj_ptr->list);
    }
    else // 内存对象充足
    {
        do
        {
            // 跳转到下一个内存池对象
            if (slab_obj_ptr->count_free == 0)
                slab_obj_ptr = container_of(list_next(&slab_obj_ptr->list), struct slab_obj, list);
            else
                break;
        } while (slab_obj_ptr != kmalloc_cache_group[index].cache_pool);
    }

    // 寻找一块可用的内存对象
    int md;
    for (int i = 0; i < slab_obj_ptr->count_free; ++i)
    {
        // 当前bmp全部被使用
        if (*slab_obj_ptr->bmp + (i >> 6) == 0xffffffffffffffffUL)
        {
            i += 63;
            continue;
        }
        md = i % 64;
        // 找到相应的内存对象
        if (*(slab_obj_ptr->bmp + (i >> 6)) & (1UL << md) == 0)
        {
            *(slab_obj_ptr->bmp + (i >> 6)) |= (1UL << md);
            ++(slab_obj_ptr->count_using);
            --(slab_obj_ptr->count_free);

            --kmalloc_cache_group[index].count_total_free;
            ++kmalloc_cache_group[index].count_total_using;

            return (void*)((char*)slab_obj_ptr->vaddr+kmalloc_cache_group[index].size*i);
        }
    }

    kerror("kmalloc(): Cannot alloc more memory: %d bytes", size);
    return NULL;
}

/**
 * @brief 通用内存释放函数
 *
 * @param address 要释放的内存地址
 * @return unsigned long
 */
unsigned long kfree(void *address)
{
    // @todo: 通用内存释放函数
}