RT-Thread-rt-thread 小内存算法源码分析RT-Thread问答社区

rt-thread 小内存算法源码分析

发布于 2024-12-21 13:14:25 浏览：16 订阅该版

[tocm]

### 小内存管理算法
这个是malloc函数的一种简单实现，通过分析代码可以了解内存分配的基本原理和方法。

#### 内存分配宏
rt-thread 有多种内存分配方法，通过宏定义选择使用哪种。
```c
#if defined(RT_USING_SMALL_MEM_AS_HEAP)
static rt_smem_t system_heap;
rt_inline void _smem_info(rt_size_t *total,
    rt_size_t *used, rt_size_t *max_used)
{
    if (total)
        *total = system_heap->total;
    if (used)
        *used = system_heap->used;
    if (max_used)
        *max_used = system_heap->max;
}
#define _MEM_INIT(_name, _start, _size) \
    system_heap = rt_smem_init(_name, _start, _size)
#define _MEM_MALLOC(_size)  \
    rt_smem_alloc(system_heap, _size)
#define _MEM_REALLOC(_ptr, _newsize)\
    rt_smem_realloc(system_heap, _ptr, _newsize)
#define _MEM_FREE(_ptr) \
    rt_smem_free(_ptr)
#define _MEM_INFO(_total, _used, _max)  \
    _smem_info(_total, _used, _max)
```

#### 结构体

```c
/*分配的小内存块的管理头*/
struct rt_small_mem_item
{
    rt_uintptr_t            pool_ptr;         /**< small memory object addr */
    rt_size_t               next;             /**< next free item */
    rt_size_t               prev;             /**< prev free item */
};

struct rt_memory
{
    struct rt_object        parent;          
    const char *            algorithm;              /**< 内存管理算法名字 */
    rt_ubase_t              address;                /**< 内存起始地址*/
    rt_size_t               total;                  /**<内存大小*/
    rt_size_t               used;                   /**< 已用内存大小 */
    rt_size_t               max;                   
};
typedef struct rt_memory *rt_mem_t;
/*内存堆管理器头*/
struct rt_small_mem
{
    struct rt_memory            parent;                 /**< inherit from rt_memory */
    rt_uint8_t                 *heap_ptr;               /**<堆起始地址指针 */
    struct rt_small_mem_item   *heap_end;               /*指向结束内存块*/
    struct rt_small_mem_item   *lfree;                  /*指向第一个空闲内存块*/
    rt_size_t                   mem_size_aligned;      
};
```

#### 初始化

```c
/*size:系统可用的堆内存大小 */
rt_smem_t rt_smem_init(const char    *name,
                     void          *begin_addr,
                     rt_size_t      size)
{
    struct rt_small_mem_item *mem;
    struct rt_small_mem *small_mem;
    rt_uintptr_t start_addr, begin_align, end_align, mem_size;
    
    small_mem = (struct rt_small_mem *)RT_ALIGN((rt_uintptr_t)begin_addr, RT_ALIGN_SIZE); /*管理结构体起始地址，8B地址对齐，就是该地址能被8整除*/
    start_addr = (rt_uintptr_t)small_mem + sizeof(*small_mem); /*small_mem起始地址，start_addr就是用来分配内存块的起始地址*/
    begin_align = RT_ALIGN((rt_uintptr_t)start_addr, RT_ALIGN_SIZE); /*可分配内存块起始地址，8B对齐，就是该地址能被8整除*/
    end_align   = RT_ALIGN_DOWN((rt_uintptr_t)begin_addr + size, RT_ALIGN_SIZE);  /*可分配内存结束地址，8B对齐，就是该地址能被8整除*/

/* alignment addr，#define SIZEOF_STRUCT_MEM    RT_ALIGN(sizeof(struct rt_small_mem_item), RT_ALIGN_SIZE) */
    if ((end_align > (2 * SIZEOF_STRUCT_MEM)) &&
        ((end_align - 2 * SIZEOF_STRUCT_MEM) >= start_addr))
    {
        /* 计算可分配内存大小，保留2 * SIZEOF_STRUCT_MEM空间，头和尾部各保留一个 rt_small_mem_item*/
        mem_size = end_align - begin_align - 2 * SIZEOF_STRUCT_MEM;
    }
    else
    {
        rt_kprintf("mem init, error begin address 0x%x, and end address 0x%x\n",
                   (rt_uintptr_t)begin_addr, (rt_uintptr_t)begin_addr + size);

return RT_NULL;
    }

rt_memset(small_mem, 0, sizeof(*small_mem));
    /*内存对象初始化*/
    rt_object_init(&(small_mem->parent.parent), RT_Object_Class_Memory, name);
    small_mem->parent.algorithm = "small";
    small_mem->parent.address = begin_align;  /*起始地址*/
    small_mem->parent.total = mem_size;       /*内存大小*/
    small_mem->mem_size_aligned = mem_size; /**<内存字节大小，内存对齐 */

/*heap起始地址指针*/
    small_mem->heap_ptr = (rt_uint8_t *)begin_align;
    /* initialize the start of the heap */
    mem        = (struct rt_small_mem_item *)small_mem->heap_ptr; /*mem指针*/
    mem->pool_ptr = MEM_FREED(small_mem);         /*最后一位清0*/
    mem->next  = small_mem->mem_size_aligned + SIZEOF_STRUCT_MEM;  /*指向end块*/
    mem->prev  = 0;

/* initialize the end of the heap */
    small_mem->heap_end        = (struct rt_small_mem_item *)&small_mem->heap_ptr[mem->next];
    small_mem->heap_end->pool_ptr = MEM_USED(small_mem);
    small_mem->heap_end->next  = small_mem->mem_size_aligned + SIZEOF_STRUCT_MEM;  /*指向自身*/
    small_mem->heap_end->prev  = small_mem->mem_size_aligned + SIZEOF_STRUCT_MEM;
    /* initialize the lowest-free pointer to the start of the heap */
    small_mem->lfree = (struct rt_small_mem_item *)small_mem->heap_ptr;

return &small_mem->parent;
}
```

**初始化后的内存分布:**
![small_mem_init.png](https://oss-club.rt-thread.org/uploads/20241221/298dabc7a64081e328e7219d551fb8c2.png.webp)
#### 分配内存函数分析

```c
/**
 * @brief 分配一块内存，内存空间不能小于size
 * @param m 内存管理器
 * @param size 请求的内存大小
 * @return 返回分配的内存指针
 */
void *rt_smem_alloc(rt_smem_t m, rt_size_t size)
{
    rt_size_t ptr, ptr2;
    struct rt_small_mem_item *mem, *mem2;
    struct rt_small_mem *small_mem;
    small_mem = (struct rt_small_mem *)m;
    /*初始化后，两个值相等，ptr就是lfree和内存块起始地址的偏移量，初始化时创建了一个内存块头，并标记为空闲*/
    for (ptr = (rt_uint8_t *)small_mem->lfree - small_mem->heap_ptr; 
         ptr <= small_mem->mem_size_aligned - size;       /*内存空间够分配size大小*/             
         ptr = ((struct rt_small_mem_item *)&small_mem->heap_ptr[ptr])->next) /*指向下一个内存块*/
    {
        mem = (struct rt_small_mem_item *)&small_mem->heap_ptr[ptr];
        /* mem is not used and at least perfect fit is possible:
        * mem->next - (ptr + SIZEOF_STRUCT_MEM) gives us the 'user data size' of mem
        内存块空闲，并且该内存块和下一块内存块之间的空间足够*/
        if ((!MEM_ISUSED(mem)) && (mem->next - (ptr + SIZEOF_STRUCT_MEM)) >= size)
        {
            /*两内存块空闲空间足够分配size大小，并且剩余空间还大于等于SIZEOF_STRUCT_MEM + MIN_SIZE_ALIGNED
            那么就创建一个新的内存块头*/
            if (mem->next - (ptr + SIZEOF_STRUCT_MEM) >=  
                (size + SIZEOF_STRUCT_MEM + MIN_SIZE_ALIGNED))
            {
                ptr2 = ptr + SIZEOF_STRUCT_MEM + size; /*指向下一个内存块，size是对齐过后的值*/

/*创建 mem2 struct,在mem后插入mem2 */
                mem2       = (struct rt_small_mem_item *)&small_mem->heap_ptr[ptr2];
                mem2->pool_ptr = MEM_FREED(small_mem);
                mem2->next = mem->next;  /*指向下一个内存块，实际使用的是偏移，非指针*/
                mem2->prev = ptr; /*指向前一个内存块，实际使用的是偏移，非指针*/
                /* and insert it between mem and mem->next
                mem2插入到mem和mem->next之间*/
                mem->next = ptr2;
                if (mem2->next != small_mem->mem_size_aligned + SIZEOF_STRUCT_MEM) /*如果mem2->next指向的不是heap_end*/
                {
                    /*mem2下一个内存块前驱指向mem2*/
                    ((struct rt_small_mem_item *)&small_mem->heap_ptr[mem2->next])->prev = ptr2; 
                }
                small_mem->parent.used += (size + SIZEOF_STRUCT_MEM); /*已使用空间*/
                if (small_mem->parent.max < small_mem->parent.used)
                    small_mem->parent.max = small_mem->parent.used;
            }
            else
            {
                small_mem->parent.used += mem->next - ((rt_uint8_t *)mem - small_mem->heap_ptr);
                if (small_mem->parent.max < small_mem->parent.used)
                    small_mem->parent.max = small_mem->parent.used;
            }
            /* set small memory object */
            mem->pool_ptr = MEM_USED(small_mem);
            if (mem == small_mem->lfree)
            {
                /* Find next free block after mem and update lowest free pointer 
                更新lfree指针，指向下一个没有使用的内存块*/
                while (MEM_ISUSED(small_mem->lfree) && small_mem->lfree != small_mem->heap_end)
                    small_mem->lfree = (struct rt_small_mem_item *)&small_mem->heap_ptr[small_mem->lfree->next];
            }
            return (rt_uint8_t *)mem + SIZEOF_STRUCT_MEM;
        }
    }
    return RT_NULL;
}
```

#### 释放内存

```c
/**
 * @brief 释放内存块
 * @param rmem 要释放的内存指针
 */
void rt_smem_free(void *rmem)
{
    struct rt_small_mem_item *mem;
    struct rt_small_mem *small_mem;
    /* Get the corresponding struct rt_small_mem_item ...
    计算内存空间对应的内存块头 */
    mem = (struct rt_small_mem_item *)((rt_uint8_t *)rmem - SIZEOF_STRUCT_MEM);
    small_mem = MEM_POOL(mem); /*根据mem查找small_mem*/
    /*判断合法性*/
    RT_ASSERT(small_mem != RT_NULL); 
    RT_ASSERT(MEM_ISUSED(mem));
    RT_ASSERT(rt_object_get_type(&small_mem->parent.parent) == RT_Object_Class_Memory);
    RT_ASSERT(rt_object_is_systemobject(&small_mem->parent.parent));
    RT_ASSERT((rt_uint8_t *)rmem >= (rt_uint8_t *)small_mem->heap_ptr &&
              (rt_uint8_t *)rmem < (rt_uint8_t *)small_mem->heap_end);
    RT_ASSERT(MEM_POOL(&small_mem->heap_ptr[mem->next]) == small_mem);
    /* ... and is now unused. */
    mem->pool_ptr = MEM_FREED(small_mem);
    if (mem < small_mem->lfree)
    {
        /* the newly freed struct is now the lowest */
        small_mem->lfree = mem;
    }
    small_mem->parent.used -= (mem->next - ((rt_uint8_t *)mem - small_mem->heap_ptr));
    /*查看释放内存块和前后内存块是否能够合并*/
    plug_holes(small_mem, mem);
}
/*查看释放内存块和前后内存块是否能够合并
m:内存管理器*/
static void plug_holes(struct rt_small_mem *m, struct rt_small_mem_item *mem)
{
    struct rt_small_mem_item *nmem;
    struct rt_small_mem_item *pmem;

/* 合并next块 */
    nmem = (struct rt_small_mem_item *)&m->heap_ptr[mem->next];
     /*next内存块空闲，不是最heap_end块，也不是自身，貌似只有heap_end才会指向自身*/
    if (mem != nmem && !MEM_ISUSED(nmem) &&                  
        (rt_uint8_t *)nmem != (rt_uint8_t *)m->heap_end)
    {
        /* if mem->next is unused and not end of m->heap_ptr,
         * combine mem and mem->next
         */
        if (m->lfree == nmem)
        {
            m->lfree = mem;
        }
        nmem->pool_ptr = 0;
        mem->next = nmem->next;
        ((struct rt_small_mem_item *)&m->heap_ptr[nmem->next])->prev = (rt_uint8_t *)mem - m->heap_ptr;
    }

/* 合并pre块 */
    pmem = (struct rt_small_mem_item *)&m->heap_ptr[mem->prev];
    if (pmem != mem && !MEM_ISUSED(pmem))
    {
        /* if mem->prev is unused, combine mem and mem->prev */
        if (m->lfree == mem)
        {
            m->lfree = pmem;
        }
        mem->pool_ptr = 0;
        pmem->next = mem->next;
        ((struct rt_small_mem_item *)&m->heap_ptr[mem->next])->prev = (rt_uint8_t *)pmem - m->heap_ptr;
    }
}
```