单片机中的内存分配

了解上位机代码的对malloc和free这两个函数都不陌生，使用内存分配和释放的目的是为了有效的利用内存。但在单片机中，彷佛是回到了石器时代，上位机中各种库函数不一定能用，即便能用也不够灵活，或者占用资源较多，出了问题也不好定位。作为一个玩转单片机的人，总不喜欢那些看不见的代码，所以特意学习了一下。
我是直接看TI 的一个协议栈中OSAL内存分配函数，思路是这样，定义一个用于内存分配的数组，这个数组就就相但于堆，需要时就从里面取一块出来，用完后有给放回去，这样就成了资源共享，提高内存利用率。每次取走一块内存，就在堆里做一个标记，标记本次被分配的内存是多大，然后把可分配内存的指针偏移相应的大小。
每一个内存块用一个两个字节的头来标记内存状态，其中低15位表示本块内存的大小，最高位表示本块内存是否已被使用。使分配函数时，得先对堆进行初始化，就是标记可用内存块大小为堆的总量-2字节大小，状态为0，即未被使用。并把内存块的索引地址指向堆第一个字节。分配内存时从索引地址往后偏移量字节后，划出指定长度的内存空间，并设置内存块的大小为指定大小，空闲标志置为1，然后再把内存所有地址知道被分配的内存块的后面，如此重复。
释放内存时，先将空闲标记置为0，然后判断被释放内存的头的地址是否小于内存当前索引地址，若小于，要将内存索引地址指到当前被释放的内存地址。比如被释放的内存块是1，当前内存索引地址是内存块3的头信息，那要将当前内存的索引地址改为内存块1的头信息地址。下次内存分配时从内存索引地址逐个查找大小满足需求的内存块，若不满足，检查下一块是否为空，若为空则判断两块内 将两块内存总和是否满足需求，若满足，就将两块内存合到一起分配，若不够再继续往下查，若相连的未被使用的内存不够，则需要找到下一个空闲的内存块 再继续找满足需求的内存块，若找到就返回分配的内存地址，若找不到就返回0，0表示分配失败。
在实际中，为了减小内存碎片问题，还要将堆分为大块区和小块去，小内存在从小块区分配，大的内存要到大块区分配。下面是代码，有详细的注释：

#include "cpu.h"
#include "OSAL_Memory.h"

#define TRUE 1
#define FALSE 0
#define NULL 0

//typedef   unsigned char  u8;
//typedef   unsigned short int u16;
//typedef   unsigned int u32;

#define halDataAlign_t   u8 //对齐方式
#define MAXMEMHEAP 4096
#define OSALMEM_IN_USE             0x8000
#define OSALMEM_HDRSZ              sizeof(osalMemHdr_t) //2
#define OSALMEM_ROUND(X) ((((X) + OSALMEM_HDRSZ - 1) / OSALMEM_HDRSZ) * OSALMEM_HDRSZ) //调整为2的整数倍
#define OSALMEM_MIN_BLKSZ (OSALMEM_ROUND((OSALMEM_HDRSZ * 2))) //8
#define OSALMEM_LL_BLKSZ (OSALMEM_ROUND(6) + (1 * OSALMEM_HDRSZ)) //8
#define OSALMEM_SMALL_BLKSZ (OSALMEM_ROUND(16)) //16
#define OSALMEM_SMALL_BLKCNT       8

#define OSALMEM_SMALLBLK_BUCKET ((OSALMEM_SMALL_BLKSZ * OSALMEM_SMALL_BLKCNT) + OSALMEM_LL_BLKSZ)//16*8+8=136
#define OSALMEM_SMALLBLK_HDRCNT (OSALMEM_SMALLBLK_BUCKET / OSALMEM_HDRSZ) // 136/2=68
#define OSALMEM_BIGBLK_IDX (OSALMEM_SMALLBLK_HDRCNT + 1) // 69
#define OSALMEM_BIGBLK_SZ (MAXMEMHEAP - OSALMEM_SMALLBLK_BUCKET - OSALMEM_HDRSZ*2)// 4096-136-2*2=3956
#define OSALMEM_LASTBLK_IDX ((MAXMEMHEAP / OSALMEM_HDRSZ) - 1) //4096/2-1=2047

#define OSALMEM_INIT              0xAA //初始化为AA
#define OSALMEM_ALOC              0x00 //分配后全设置为0
#define OSALMEM_REIN              0xFF //释放后全设置为FF


#pragma pack(1)//定义结构体按字节对齐
typedef struct {
  //低15位代表长度
  unsigned len : 15;
  //最高位代表使用情况，1表示被使用，0表示未被使用
  unsigned inUse : 1;
} osalMemHdrHdr_t;
#pragma pack()

typedef union {
  unsigned char alignDummy;//按字节对齐作用
  unsigned short int val;
  osalMemHdrHdr_t hdr;
} osalMemHdr_t;


 osalMemHdr_t theHeap[MAXMEMHEAP / OSALMEM_HDRSZ];
static osalMemHdr_t *ff1; // 第一个空闲块的指针.
static u8 osalMemStat; // Discrete status flags: 0x01 = kicked.


//memset
static void _memset(void* databuf,u8 value,u16 length)
{
    u16 i;
    u8 * buf=(u8*)databuf;

    if(!buf)
        return;
    for(i=0;i<length;i++)
    {
        buf[i]=value;
    }
}


//使用内存分配函数前须执行过初始化函数
void osal_mem_init(void)
{
   osalMemHdr_t *tmp;
  _memset(theHeap, OSALMEM_INIT, MAXMEMHEAP);


  // Setup a NULL block at the end of the heap for fast comparisons with zero.
  theHeap[OSALMEM_LASTBLK_IDX].val = 0;

  //将内存分为小块区和大块区，便于快速分配内存
  // Setup the small-block bucket.
  ff1 = theHeap;
  ff1->val = OSALMEM_SMALLBLK_BUCKET; // OSALMEM_SMALLBLK_BUCKET=136 ，Set 'len' & clear 'inUse' field.

  // Set 'len' & 'inUse' fields - this is a 'zero data bytes' lifetime allocation to block the
  // small-block bucket from ever being coalesced with the wilderness.
  theHeap[OSALMEM_SMALLBLK_HDRCNT].val = (OSALMEM_HDRSZ | OSALMEM_IN_USE);//OSALMEM_SMALLBLK_HDRCNT=68

   //内存大块区
  // Setup the wilderness.
  theHeap[OSALMEM_BIGBLK_IDX].val = OSALMEM_BIGBLK_SZ; // OSALMEM_BIGBLK_IDX=69 Set 'len' & clear 'inUse' field.



  tmp = osal_mem_alloc(1);
  CPU_IntDis(); // 挂起中断.

  ff1 = tmp - 1; // Set 'ff1' to point to the first available memory after the LL block.
  osal_mem_free(tmp);
  osalMemStat = 0x01; // Set 'osalMemStat' after the free because it enables memory profiling.

  CPU_IntEn();//使能中断 // 恢复中断
}


void *osal_mem_alloc( u16 size )
{
    osalMemHdr_t *prev = NULL;
    osalMemHdr_t *hdr;

    u8 coal = 0;

    size += OSALMEM_HDRSZ;

    // Calculate required bytes to add to 'size' to align to halDataAlign_t.
    if ( sizeof( halDataAlign_t ) == 2 )
    {
        size += (size & 0x01);//使size成为偶数，即2的倍数
    }
    else if ( sizeof( halDataAlign_t ) != 1 )
    {
        const u8 mod = size % sizeof( halDataAlign_t );

        if ( mod != 0 )
        {
            size += (sizeof( halDataAlign_t ) - mod);//使size成为halDataAlign_t的倍数
        }
    }

    CPU_IntDis(); // 挂起中断.

    // Smaller allocations are first attempted in the small-block bucket, and all long-lived
    // allocations are channeled into the LL block reserved within this bucket.
    if ((osalMemStat == 0) || (size <= OSALMEM_SMALL_BLKSZ))//小块的内存
    {
        hdr = ff1;
    }
    else//大块的内存
    {
        hdr = (theHeap + OSALMEM_BIGBLK_IDX);
    }

    do
    {
        if ( hdr->hdr.inUse )//如果本次查询的内存块已被使用，跳到下一块内存，直到找到连续的满足大小的一片内存
        {
          coal = 0;//扩充内存标记清0
        }
        else
        {
          if ( coal != 0 )//上一块内存块空间不够
          {
            prev->hdr.len += hdr->hdr.len;//将相邻两内存块的大小相加

            if ( prev->hdr.len >= size )//相加后满足需求
            {
              hdr = prev;
              break;
            }
          }
          else
          {
            if ( hdr->hdr.len >= size )
            {
              break;
            }

            coal = 1;//当前内存块小于要分配的内存大小
            prev = hdr;//备份内存块地址
          }
        }

        hdr = (osalMemHdr_t *)((u8 *)hdr + hdr->hdr.len);//跳到下一个内存块

        if ( hdr->val == 0 )
        {
          hdr = NULL;//内存分配失败
          break;
        }
    } while (1);

    if ( hdr != NULL )
    {
        u16 tmp = hdr->hdr.len - size;//计算hdr剩余内存

        // Determine whether the threshold for splitting is met.
        if ( tmp >= OSALMEM_MIN_BLKSZ )//内存是否用完
        {
          // Split the block before allocating it.
          osalMemHdr_t *next = (osalMemHdr_t *)((u8 *)hdr + size);
          next->val = tmp; // Set 'len' & clear 'inUse' field.记录剩下的内存的大小
          hdr->val = (size | OSALMEM_IN_USE); // Set 'len' & 'inUse' field.标记有size大小的内存已被使用

        }
        else//内存已用完
        {

          hdr->hdr.inUse = TRUE;
        }

        if ((osalMemStat != 0) && (ff1 == hdr))
        {
          ff1 = (osalMemHdr_t *)((u8 *)hdr + hdr->hdr.len);//更新空闲内存块的起始地址
        }

        hdr++;//内存标记指针后的内存才是分配到的内存，所以要++
    }

    CPU_IntEn();//使能中断
    _memset(hdr,OSALMEM_ALOC,size-OSALMEM_HDRSZ);//调试用
    return (void *)hdr;
}



void osal_mem_free(void *ptr)

{
  osalMemHdr_t *hdr = (osalMemHdr_t *)ptr - 1;


   CPU_IntDis(); // 挂起中断.
  _memset(ptr,OSALMEM_REIN ,hdr->hdr.len-OSALMEM_HDRSZ);//调试用
  hdr->hdr.inUse = FALSE;

  if (ff1 > hdr)//如果被释放的内存地址小于空闲内存块的起始地址，则将其合并
  {
    ff1 = hdr;
  }

    CPU_IntEn();//使能中断
}