Porting RT thread to s5p4418 (II): dynamic memory management

memory management

stay RT-Thread Divided into dynamic Memory management and static state memory management . Static is also called Memory pool management , Dynamic is called Memory heap management .

Memory heap ：

The government provides three management methods .

• Small memory management . The application was made on a large piece of 、 The contiguous memory is divided into matching small memory blocks as required ; On release , Return to the heap management system . Each memory block contains a data header for management , Use the bidirectional linked list to manage the used blocks and free blocks .
• slab Management algorithm .TODO！
• memheap Management algorithm . It is applicable to the memory heap with multiple addresses that can be discontinuous .

Memory pool ：

When creating a memory pool, first apply to the system for a large block of memory , And then divide it into Same size Multiple small memory blocks of , Small memory blocks are connected directly through linked lists （ This linked list is also called free linked list ）. Every time it's distributed , Take the first memory block on the chain head from the free list , To the applicant .

---

Small memory management algorithm implementation

Three core functions

• void rt_system_heap_init(void *begin_addr, void *end_addr);
• void *rt_malloc(rt_size_t size);
• void rt_free(void *rmem);

---

rt_system_heap_init Initializing the heap

void rt_system_heap_init(void *begin_addr, void *end_addr)
{
    
    struct heap_mem *mem;
    rt_ubase_t begin_align = RT_ALIGN((rt_ubase_t)begin_addr, RT_ALIGN_SIZE);
    rt_ubase_t end_align = RT_ALIGN_DOWN((rt_ubase_t)end_addr, RT_ALIGN_SIZE);

    if((end_align > (2 * SIZEOF_STRUCT_MEM)) &&
        ((end_align - 2 * SIZEOF_STRUCT_MEM) >= begin_align)){
      //  Save at least two heap_mem
        mem_size_aligned = end_align - begin_align - 2 * SIZEOF_STRUCT_MEM;
    }else{
    
        printf("mem init, error begin address 0x%x, and end address 0x%x\n",
                   (rt_uint32_t)begin_addr, (rt_uint32_t)end_addr);
        
        return;
    }

    heap_ptr = (rt_uint8_t *)begin_align;

    mem = (struct heap_mem *)heap_ptr;
    mem->magic = HEAP_MAGIC;
    mem->used = 0;
    mem->prev = 0;  // pre、next Is relative to heap_ptr The offset 
    mem->next = mem_size_aligned + SIZEOF_STRUCT_MEM;   // mem_size_aligned Yes, subtract two heap_mem The size of the back 

    heap_end = (struct heap_mem *)&heap_ptr[mem->next];
    heap_end->magic = HEAP_MAGIC;
    heap_end->used = 1;
    heap_end->prev = mem->next;
    heap_end->next = mem->next;

    rt_sem_init(&heap_sem, "heap", 1, RT_IPC_FLAG_FIFO);   //  Initialize memory management specific semaphores 

    lfree = (struct heap_mem *)heap_ptr; // lfree Record the top available memory block 
}

First, explain the memory control block structure , Each memory block requested contains such a header ;

/*  Memory control block  */
struct heap_mem
{
    
    /* magic and used flag */
    rt_uint16_t magic;
    rt_uint16_t used;

    rt_size_t next, prev;
};

• mem.magic They are called magic numbers , It will be initialized to 0x1ea0, The memory block used to mark is a memory data for memory management ;
• mem.used Indicates whether the current memory block is being used ;
• mem.next and mem.prev Used for the management of two-way linked lists ;

---

When initializing the memory heap , You need to pass in the start and end addresses , Customize the memory size for the heap by writing link scripts , And the location of the stack . The tail header indicates that there is no memory space to allocate after this address .lfree Record the current top free block of the system .

---

rt_malloc Application memory

void *rt_malloc(rt_size_t size){
    
    struct heap_mem *mem, *mem2;
    rt_size_t ptr, ptr2;

    if(size == 0){
    
        return RT_NULL;
    }

    size = RT_ALIGN(size, RT_ALIGN_SIZE);

    if(size > mem_size_aligned){
    
        printf("no memory %d\r\n", size);

        return RT_NULL;
    }

    if(size < MIN_SIZE_ALIGNED){
    
        size = MIN_SIZE_ALIGNED;
    }

    /*  Semaphore protection resources  */
    rt_sem_take(&heap_sem, RT_WAITING_FOREVER);

    /* ptr Is the offset of free memory ,ptr < mem_size_aligned - size Indicates that there may be allocable blocks  */
    for(ptr = (rt_uint8_t *)lfree - heap_ptr; ptr < mem_size_aligned - size; ptr = ((struct heap_mem *)&heap_ptr[ptr])->next){
    
        mem = (struct heap_mem *)&heap_ptr[ptr];

        /* mem->next - (ptr + SIZEOF_STRUCT_MEM) Is the current memory block size  */
        if((!mem->used) && mem->next - (ptr + SIZEOF_STRUCT_MEM) >= size){
    
            
            /*  If the memory block is large enough , Initialize the rest into a free block  */
            if(mem->next - (ptr + SIZEOF_STRUCT_MEM) >= size + SIZEOF_STRUCT_MEM + MIN_SIZE_ALIGNED){
    
                ptr2 = ptr + SIZEOF_STRUCT_MEM + size;

                mem2 = (struct heap_mem *)&heap_ptr[ptr2];
                mem2->magic = HEAP_MAGIC;
                mem2->used = 0;
                mem2->prev = ptr;
                mem2->next = mem->next;

                mem->next = ptr2;
                mem->used = 1;

                if(mem2->next != mem_size_aligned + SIZEOF_STRUCT_MEM){
    
                    ((struct heap_mem *)&heap_ptr[mem2->next])->prev = ptr2;
                }      
            }else{
    
                mem->used = 1;
            }

            /*  Look for new 、 The first free block  */
            if(mem == lfree){
    
                while(lfree->used && lfree != heap_end)
                    lfree = (struct heap_mem *)&heap_ptr[lfree->next];
            }

            rt_sem_release(&heap_sem);
            
            return (rt_uint8_t *)mem + SIZEOF_STRUCT_MEM;
        }
    }

    rt_sem_release(&heap_sem);

    return RT_NULL;
}

from lfree Look back for more than size Free block of , If the memory block found is large enough , Initialize the rest into a new free block . Simultaneous updating lfree

---

rt_free Free memory

void rt_free(void *rmem){
    
    struct heap_mem *mem;

    if(rmem == RT_NULL){
    
        printf("addr is invalid %d\r\n", 0);

        return;
    }

    if((rt_uint8_t *)rmem < heap_ptr || (rt_uint8_t *)rmem >= heap_end){
    
        printf("addr is invalid %d\r\n", -1);

        return;
    }

    /*  Acquisition semaphore  */
    rt_sem_take(&heap_sem, RT_WAITING_FOREVER);

    mem = (struct heap_mem *)((rt_uint8_t *)rmem - SIZEOF_STRUCT_MEM);
    if (!mem->used || mem->magic != HEAP_MAGIC)
    {
    
        printf("to free a bad data block: %c\n", ' ');
        printf("mem: 0x%08x, used flag: %d, magic code: 0x%04x\n", mem, mem->used, mem->magic);
    }
    RT_ASSERT(mem->used);
    RT_ASSERT(mem->magic == HEAP_MAGIC);    //  For the top if

    /*  Mark as unused  */
    mem->used = 0;
    mem->magic = HEAP_MAGIC;

    if(mem < lfree){
    
        lfree = mem;
    }

    /*  Used to merge unused memory blocks before and after  */
    plug_holes(mem);

    rt_sem_release(&heap_sem);

}

On release , modify .used A sign is enough , And then call plug_holes(mem) Unused memory blocks before and after merging .

---

Dynamic memory management is the dynamic creation of threads , And the premise of other kernel applications .

Engineering documents

rtt2a9_heap
Key 1 Request memory and write values , Key 2 Read value and release ;