自写单片机malloc,高效利用ram,不再有内存碎片

2019-04-15 12:37发布

单片机应用中,malloc/free产生内存碎片的原因: 标准内存动态分配是动态链表进行管理。由于malloc返回的是一个指针再加上单片机没有mmu,使得分配的指针就像一个个钉子钉在内存中了。这就导致内存管理非常困难,从而产生我们常说的内存碎片。 我们来举一个极端的例子,导致大量内存碎片: 1. 单片机的RAM为1Kbyte,为了说明和计算方便我们忽略掉链表占用的空间,只计算实际存储空间大小。 2. 申请64块内存空间,每块是16字节,那么就会分配完1k字节的空间。即:
for(int i=0; i<64; i++){
    ptr[i] = malloc(16);
} 3. 然后释放掉偶数块内存空间,即:
for(int i=0; i<64; i+=2){
    free(ptr[i] );
} 4. 于是我们释放掉了一半的RAM空间,即有512字节的空间,但是都是非连续的。32块16字节的非连续空间,所以要分配出大于16字节的内存块是分配不出来的。有512字节的空间但只能分配小于16字节的连续空间(除非使用calloc分配非连续空间),在某些场合原本单片机RAM空间就很急,再加上这种不充分的使用使得程序稳定性大打折扣。 鉴于各中原因本人自己编写了一个内存管理,适合单片机使用的内存管理分配。 算法原理:
定义一个数组作为动态分配的堆空间,低地址空间保存管理数据,高地址空间实际分配给用户的缓存(类似堆栈使用,分配是往中间靠拢),free时移动高地址用户空间(以时间换空间),腾出多余未使用的空间,等待malloc来分配。 #include "mem_malloc.h" static unsigned int sum = 0; static char mem[MEM_SIZE]; #define DEBUG_EN 0 #define MEM_START &mem[0] #define MEM_END &mem[MEM_SIZE] #define BLK_SIZE sizeof(mem_block) void print_mem_info(void){ printf("------------mem_info-------------- "); printf("sizeof(mem_block)=%d ", BLK_SIZE); printf("MEM_START = %d(0x%x) ", (int)MEM_START, (int)MEM_START); printf("MEM_END = %d(0x%x) ", (int)MEM_END, (int)MEM_END); printf("MEM_SIZE = %d(0x%x) ", (int)MEM_SIZE, (int)MEM_SIZE); printf("---------------------------------- "); } void print_hex(char *data, int len){ for(int i=0; imem_ptr-(MEM_START + BLK_SIZE*sum); if(all_size <= free_blk){ tmp_blk.mem_ptr = ptr_blk->mem_ptr - msize; tmp_blk.mem_size = msize; tmp_blk.mem_index = ptr_blk->mem_index + 1; memcpy(MEM_START + BLK_SIZE*sum, &tmp_blk, BLK_SIZE); sum = sum + 1; #if DEBUG_EN printf("mem_ptr = 0x%x ", (int)tmp_blk.mem_ptr); printf("mem_size = 0x%x ", tmp_blk.mem_size); printf("mem_index = 0x%x ", tmp_blk.mem_index); #endif return tmp_blk.mem_index; } }else{ if(all_size <= MEM_SIZE){ tmp_blk.mem_ptr = MEM_END - msize; tmp_blk.mem_size = msize; tmp_blk.mem_index = 1; memcpy(MEM_START, &tmp_blk, BLK_SIZE); sum = 1; #if DEBUG_EN printf("mem_ptr = 0x%x ", (int)tmp_blk.mem_ptr); printf("mem_size = 0x%x ", tmp_blk.mem_size); printf("mem_index = 0x%x ", tmp_blk.mem_index); #endif return 1; } } return 0; } void *mem_buffer(int id){ for(int i=0; imem_index){ return ptr_blk->mem_ptr; } } return NULL; } void mem_free(int id){ for(int i=0; imem_index){ mem_block *ptr_old; if(i != (sum-1)){ int offset = ptr_blk->mem_size; int move_size = 0; int n = sum - i; mem_block *ptr_tmp; for(int j=1; jmem_size; } //memmove(); char *dst_addr = ptr_tmp->mem_ptr + move_size + offset - 1; char *src_addr = ptr_tmp->mem_ptr + move_size - 1; for(int j=move_size; j>0; j--){ *dst_addr-- = *src_addr--; } int len = dst_addr - src_addr + 1; memset(src_addr, 0, len); for(int j=0; j<(n-1); j++){ ptr_tmp = (mem_block *)(MEM_START + BLK_SIZE*(i+j)); ptr_old = (mem_block *)(MEM_START + BLK_SIZE*(i+j+1)); memcpy(ptr_tmp, ptr_old, BLK_SIZE); ptr_tmp->mem_ptr += offset; } }else{ ptr_old = (mem_block *)(MEM_START + BLK_SIZE*i); memset(ptr_old->mem_ptr, 0, ptr_old->mem_size); } memset(ptr_old, 0, BLK_SIZE); sum = sum - 1; break; } } } main.c #include "mem_malloc.h" char mem_id[10]={0}; void test_malloc(int i, int size){ printf("------test_malloc------- "); mem_id[i] = mem_malloc(size); if(mem_id[i] == 0){ printf("malloc --- fail "); printf("size=%d ", size); }else{ char *p = mem_buffer(mem_id[i]); memset(p, i, size); printf("p = 0x%x, id=%d, size=%d ", (int)p, mem_id[i], size); } print_mem_hex(MEM_SIZE); } void test_buffer(int i, int size){ printf("------test_buffer------- "); printf("id = %d, size=%d ", mem_id[i], size); char *p = mem_buffer(mem_id[i]); if(p != NULL){ memset(p, 0xf0+i, size); print_mem_hex(MEM_SIZE); } } void test_free(int id){ printf("------test_free------- "); printf("id = %d ", mem_id[id]); mem_free(mem_id[id]); print_mem_hex( MEM_SIZE); } void main(void){ print_mem_info(); test_malloc(1, 10); test_malloc(2, 8); test_malloc(3, 20); test_free(2); test_malloc(4, 10); test_free(1); test_malloc(5, 20); test_malloc(6, 10); test_malloc(7, 10); test_free(6); test_malloc(8, 13); test_buffer(5, 20); test_free(4); test_buffer(3, 20); test_malloc(9, 15); test_malloc(10, 15); } 结果: ------------mem_info--------------
sizeof(mem_block)=12
MEM_START = 134525056(0x804b080)
MEM_END   = 134525184(0x804b100)
MEM_SIZE  = 128(0x80)    //方便演示以128字节空间测试
----------------------------------
------test_malloc-------
p = 0x804b0f6, id=1, size=10
f6 b0 04 08 0a 00 00 00 01 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 01 01 
01 01 01 01 01 01 01 01                       //第一次分配的10个字节空间

------test_malloc-------
p = 0x804b0ee, id=2, size=8
f6 b0 04 08 0a 00 00 00 01 00 00 00 
ee b0 04 08 08 00 00 00 02 00 00 00 

00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 
00 00 02 02 02 02 02 02 02 02 01 01   // 第二次分配的8个字节空间
01 01 01 01 01 01 01 01 
------test_malloc-------
p = 0x804b0da, id=3, size=20
f6 b0 04 08 0a 00 00 00 01 00 00 00 
ee b0 04 08 08 00 00 00 02 00 00 00 
da b0 04 08 14 00 00 00 03 00 00 00 

00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 03 03 03 03 03 03 
03 03 03 03 03 03 03 03 03 03 03 03   //第三次分配的20个字节空间
03 03
02 02 02 02 02 02 02 02 01 01 
01 01 01 01 01 01 01 01 
------test_free-------
id = 2
f6 b0 04 08 0a 00 00 00 01 00 00 00 
e2 b0 04 08 14 00 00 00 03 00 00 00 

00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 
00 00 03 03 03 03 03 03 03 03 03 03 
03 03 03 03 03 03 03 03 03 03 01 01  //释放掉了第二次分配的8字节空间
01 01 01 01 01 01 01 01 

------test_malloc-------
p = 0x804b0d8, id=4, size=10
f6 b0 04 08 0a 00 00 00 01 00 00 00 
e2 b0 04 08 14 00 00 00 03 00 00 00 
d8 b0 04 08 0a 00 00 00 04 00 00 00
 
00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 04 04 04 04 04 04 04 04  //第四次分配10字节空间
04 04
03 03 03 03 03 03 03 03 03 03 
03 03 03 03 03 03 03 03 03 03 01 01 
01 01 01 01 01 01 01 01 
------test_free-------
id = 1
ec b0 04 08 14 00 00 00 03 00 00 00 
e2 b0 04 08 0a 00 00 00 04 00 00 00 

00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 
00 00 04 04 04 04 04 04 04 04 04 04 
03 03 03 03 03 03 03 03 03 03 03 03 
03 03 03 03 03 03 03 03                       //释放掉了第一次分配的10字节空间

------test_malloc-------
p = 0x804b0ce, id=5, size=20
ec b0 04 08 14 00 00 00 03 00 00 00 
e2 b0 04 08 0a 00 00 00 04 00 00 00 
ce b0 04 08 14 00 00 00 05 00 00 00 

00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 05 05 05 05 05 05 
05 05 05 05 05 05 05 05 05 05 05 05  //第五次分配20字节空间
05 05
04 04 04 04 04 04 04 04 04 04 
03 03 03 03 03 03 03 03 03 03 03 03 
03 03 03 03 03 03 03 03 
------test_malloc-------
p = 0x804b0c4, id=6, size=10
ec b0 04 08 14 00 00 00 03 00 00 00 
e2 b0 04 08 0a 00 00 00 04 00 00 00 
ce b0 04 08 14 00 00 00 05 00 00 00 
c4 b0 04 08 0a 00 00 00 06 00 00 00 

00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 06 06 06 06   //第六次分配10字节空间
06 06 06 06 06 06
05 05 05 05 05 05 
05 05 05 05 05 05 05 05 05 05 05 05 
05 05 04 04 04 04 04 04 04 04 04 04 
03 03 03 03 03 03 03 03 03 03 03 03 
03 03 03 03 03 03 03 03 
------test_malloc-------
malloc --- fail
size=10
ec b0 04 08 14 00 00 00 03 00 00 00 
e2 b0 04 08 0a 00 00 00 04 00 00 00 
ce b0 04 08 14 00 00 00 05 00 00 00 
c4 b0 04 08 0a 00 00 00 06 00 00 00 

00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 06 06 06 06   //剩余20字节-12字节=8字节,所以第七次分配10字节失败
06 06 06 06 06 06 05 05 05 05 05 05 
05 05 05 05 05 05 05 05 05 05 05 05 
05 05 04 04 04 04 04 04 04 04 04 04 
03 03 03 03 03 03 03 03 03 03 03 03 
03 03 03 03 03 03 03 03 

------test_free-------
id = 6
ec b0 04 08 14 00 00 00 03 00 00 00 
e2 b0 04 08 0a 00 00 00 04 00 00 00 
ce b0 04 08 14 00 00 00 05 00 00 00 

00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 05 05 05 05 05 05   //释放掉了第六次分配的10字节空间
05 05 05 05 05 05 05 05 05 05 05 05 
05 05 04 04 04 04 04 04 04 04 04 04 
03 03 03 03 03 03 03 03 03 03 03 03 
03 03 03 03 03 03 03 03
 
------test_malloc-------
p = 0x804b0c1, id=6, size=13
ec b0 04 08 14 00 00 00 03 00 00 00 
e2 b0 04 08 0a 00 00 00 04 00 00 00 
ce b0 04 08 14 00 00 00 05 00 00 00 
c1 b0 04 08 0d 00 00 00 06 00 00 00 

00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 08 08 08 08 08 08 08   //第八次分配13字节空间
08 08 08 08 08 08
05 05 05 05 05 05 
05 05 05 05 05 05 05 05 05 05 05 05 
05 05 04 04 04 04 04 04 04 04 04 04 
03 03 03 03 03 03 03 03 03 03 03 03 
03 03 03 03 03 03 03 03 
------test_buffer-------
id = 5, size=20
ec b0 04 08 14 00 00 00 03 00 00 00 
e2 b0 04 08 0a 00 00 00 04 00 00 00 
ce b0 04 08 14 00 00 00 05 00 00 00 
c1 b0 04 08 0d 00 00 00 06 00 00 00 

00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 08 08 08 08 08 08 08 
08 08 08 08 08 08 f5 f5 f5 f5 f5 f5 
f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5        //修改第五次分配的空间内容

f5 f5 04 04 04 04 04 04 04 04 04 04 
03 03 03 03 03 03 03 03 03 03 03 03 
03 03 03 03 03 03 03 03 
------test_free-------
id = 4
ec b0 04 08 14 00 00 00 03 00 00 00 
d8 b0 04 08 14 00 00 00 05 00 00 00 
cb b0 04 08 0d 00 00 00 06 00 00 00 

00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 08 08 08 08 08 08 08 08 08 
08 08 08 08 f5 f5 f5 f5 f5 f5 f5 f5 
f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5         //释放第四次分配的10字节空间
03 03 03 03 03 03 03 03 03 03 03 03 
03 03 03 03 03 03 03 03 

------test_buffer-------
id = 3, size=20
ec b0 04 08 14 00 00 00 03 00 00 00 
d8 b0 04 08 14 00 00 00 05 00 00 00 
cb b0 04 08 0d 00 00 00 06 00 00 00 

00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 08 08 08 08 08 08 08 08 08 
08 08 08 08 f5 f5 f5 f5 f5 f5 f5 f5 
f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 
f3 f3 f3 f3 f3 f3 f3 f3 f3 f3 f3 f3      //修改第三次分配的空间内容
f3 f3 f3 f3 f3 f3 f3 f3 

------test_malloc-------
p = 0x804b0bc, id=7, size=15
ec b0 04 08 14 00 00 00 03 00 00 00 
d8 b0 04 08 14 00 00 00 05 00 00 00 
cb b0 04 08 0d 00 00 00 06 00 00 00 
bc b0 04 08 0f 00 00 00 07 00 00 00
 
00 00 00 00 00 00 00 00 00 00 00 00 
09 09 09 09 09 09 09 09 09 09 09 09  //第九次分配15字节空间
09 09 09
08 08 08 08 08 08 08 08 08 
08 08 08 08 f5 f5 f5 f5 f5 f5 f5 f5 
f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 
f3 f3 f3 f3 f3 f3 f3 f3 f3 f3 f3 f3 
f3 f3 f3 f3 f3 f3 f3 f3 
------test_malloc-------
malloc --- fail
size=15
ec b0 04 08 14 00 00 00 03 00 00 00 
d8 b0 04 08 14 00 00 00 05 00 00 00 
cb b0 04 08 0d 00 00 00 06 00 00 00 
bc b0 04 08 0f 00 00 00 07 00 00 00 

00 00 00 00 00 00 00 00 00 00 00 00 
09 09 09 09 09 09 09 09 09 09 09 09   //剩余12字节-12字节=0字节,所以第十次分配15字节失败
09 09 09 08 08 08 08 08 08 08 08 08 
08 08 08 08 f5 f5 f5 f5 f5 f5 f5 f5 
f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 
f3 f3 f3 f3 f3 f3 f3 f3 f3 f3 f3 f3 
f3 f3 f3 f3 f3 f3 f3 f3 
源码:https://github.com/chenqy2018/mem_malloc