自制嵌入式实时操作系统
内存申请的最终目的就是要满足用户的申请找到一块合适的、空闲的内存区域并将这部分的内存的起始地址返回给用户。为了达到这一目的操作系统首先需要规划出一部分内存区域作为堆内存，之后每当有用户程序向操作系统申请内存时，操作系统则在堆内存中查找到一块合适内存区域，在查找过程中尽量减少用时。当用户申请内存后，还可以对这部分内存进行释放操作，操作系统将这部分内存回收到堆当中，表示其为可用内存区域，以便为其它用户申请内存时再次使用。下面我们将分别介绍并实现内存的申请和释放。
一、内存申请
我们可以预先定义一个全局变量区域，表示堆内存，例如在Cortex-M中我们定义20K的内存为操作系统的堆内存，这部分内存不包括程序中已经定义的全局变量：
#ifndef MM_SIZE_HEAP
#define MM_SIZE_HEAP (1024 * 20)
#endif
用户程序通常使用malloc(size_t size)函数来向操作系统申请内存，其中size表示需要申请内存的大小。接下来我们需要完成malloc(size_t size)函数的实现部分，根据用户需要申请内存的大小从堆内存中找到一个可以满足这样大小的内存区域，并将这个区域的内存区域地址返回给用户。于是，内存申请的关键问题就是如何在堆内存中找到一块刚好满足用户申请大小的内存了。我们需要定义一个结构，用于表示内存的可用块和已使用块：
//内存块实际结构如下
//block[0]: |----pre----|---next----|-use_flag-|-malloc return memory address-----|
//block[1]: |----pre----|---next----|-use_flag-|-malloc return memory address-----|
//block[2]: |----pre----|---next----|-use_flag-|-malloc return memory address-----|
//...... : ......
//block[n]: |----pre----|---next----|-use_flag-|-malloc return memory address-----|
//内存块结构
typedef struct mm_heap_s
{
//内存块前驱指针
struct mm_heap_s *pre;
//内存块后继指针
struct mm_heap_s *next;
//使用标识
unsigned char use_flag;
//内存块可用大小
unsigned int size;
} mm_heap_s;
我们需要为堆内存进行初始化，表示当前堆内存中可用的区域总大小为整个堆内存大小减去块内存节点结构体大小，其前一个节点内存块和后一个节点内存块均为空，使用状态为未使用，初始化堆内存的程序代码如下：
void mm_init(void)
{
//初始化堆内存区域为0
for (int i = 0; i < MM_SIZE_HEAP; i++)
{
mm_heap[i] = 0;
}
p_head = (mm_heap_s*) &mm_heap[0]; //内存块头节点
p_head->pre = NULL; //前一个节点为空
p_head->next = NULL; //后一个节点为空
p_head->use_flag = 0; //空闲状态
p_head->size = MM_SIZE_HEAP - sizeof(mm_heap_s) - sizeof(void*); //可用区域大小
}
如下图：
其中void *start_addr就是我们所说的用于指向当前内存块的起始地址的指针。接下来我们需要从空闲的块中查找到一个大于用户申请的内存大小的内存块，并将这一个内存块一分为二，将第一小块的可用空间大小分配为用户需要的大小并标记为已使用并将其使用地址返回给用记，之后将剩余的内存区域分配为第二小块并标记为未使用状态。如果遍历了所有的内存块，都无法找到一个大于用户需要申请的内存区域，则向用户返回空指针，表示申请内存失败。具体实现代码如下：
//内存申请算法
void* mm_alloc(unsigned int size)
{
//根据用户申请的内存做内存对齐，等到实际申请内存大小，避免内存碎片
unsigned int alloc_size = MM_ALIGN_UP(size + SIZEOF_MM_ALLOCNODE);
//最终申请的内存地址
void *addr = NULL;
//申请到的内存块
mm_heap_s *p_ret = NULL;
//获取内存块游标
mm_heap_s *p = p_cursor;
if (p == NULL)
{
p = p_head;
}
//在内存块中循环查找合适的空闲块
while (1)
{
//printf("malloc p %x %d\n", p, p->use_flag);
//如果当前块为空闲块则进行后续大小判断处理
if (!p->use_flag)
{
//尝试将当前块根据申请内存的大小分割成两个小块
mm_heap_s *mm_new = mm_split(p, alloc_size);
//如果分割小块成功，则内存申请成功
if (mm_new != NULL)
{
//设置游标
p_cursor = p;
//设置返回内存块
p_ret = p;
//设置新内存地址
p = mm_new;
//跳转到申请成功标签
goto _found;
}
//如果分割内存块失败，则判断当前空闲块的可用大小时否满足申请内存大小
//如果满足，则将当前空闲块直接分配给用户
if (alloc_size + sizeof(mm_heap_s) + sizeof(void*) <= p->size)
{
//设置游标
p_cursor = p;
//设置返回内存块
p_ret = p;
//设置p为下一个节点
p = p->next;
//跳转到申请成功标签
goto _found;
}
}
//如果内存块链表结束，则从头开始
if (p->next == NULL)
{
//从头再来
p = p_head;
}
else
{
//移动指针到下一个节点
p = p->next;
}
//如果所有节点都已经遍历，且没有找到合适的空闲块
if (p == p_cursor)
{
//返回内存申请失败标签
goto _not_found;
}
}
////如果内存块链表结束
if (p->next == NULL)
{
//返回内存申请失败标签
goto _not_found;
}
//申请内存成功
_found: ;
//设置分配块使用标记为已使用
p_ret->use_flag = 1;
//设置返回地址为当前块地址
addr = p_ret;
//返回地址增加块头大小，即用户实际可用地址
addr += sizeof(mm_heap_s);
//回返内存地址
return addr;
//申请内存失败
_not_found: ;
return NULL;
}
//将一个内存块分割成两个子块
mm_heap_s* mm_split(mm_heap_s *p, unsigned int size)
{
//如果需要分割的内存不足，则直接返回NULL,表示分割失败
//计算方式：第1块内存头 + 第1块大小 + 第1块最后4字节指针 + 第2块内存头 + 第2块大小 + 第2块最后4字节指针
if (p->size <= 2 * sizeof(mm_heap_s) + 2 * sizeof(void*) + size)
{
return NULL;
}
//申请内存地址
void *addr = p;
//返回块
mm_heap_s *ret = addr + sizeof(mm_heap_s) + sizeof(void*) + size;
//返回块的前驱为p
ret->pre = p;
//返回块的后继为p的后继
ret->next = p->next;
//计算返回块的大小
ret->size = p->size - size - sizeof(mm_heap_s) - sizeof(void*);
//使用使用标记为空闲
ret->use_flag = 0;
//设置新内存块最后4字节指针
mm_set_self(ret);
//设置p的后继为新块
p->next = ret;
//设置p的可用大小
p->size = size;
//设置p的最后4字节指针
mm_set_self(p);
return ret;
}
//设置当前内存块中最后的4个字节为指向当前块的指针
int mm_set_self(mm_heap_s *p)
{
//设置内存块最后4字节地址为当前块内存地址
mm_heap_s **self = (mm_heap_s**) mm_self_pointer(p);
*self = p;
return 0;
}
二、内存释放
内存的释放操作与申请刚好相反，我们需要将用户已经申请的内存区域重新放入堆内存中，并将其标记为空闲内存。需要注意的是，当一个内存块被释放之后，除了将其内存标记置为0表示空闲之外，还应该去判断其相邻的两个内存块是否是空闲块，如果其前一个节点的内存块也是空闲块，则需要将当前内存块与前一个内存块合并为一个更大的内存块；如果其后一个内存块也是一个空闲块，则需要将当前内存块与后一个内存块合并为一个更大的内存块；如果其前后两个内存块均为空闲块，则需要将这三个内存块合并为一个更大的内存块。这是一个非常重要且必要的功能实现。操作系统必需完成这样内存块的合并功能，否则当用户多次频繁申请和释放内存后，内存可用区域将会变成多个未使用小内存块，即使这个小的内存块的可用的总大小大于用户需要申请的内存大小，但由于多个相邻的小内存块没有被合并成更大的内存块，因此也无法为用户查找到可用内存。因此我们必须实现相邻空闲内存块的合并功能。
//内存释放，合并相邻的空闲块，有效避免内存碎块残留
void mm_free(void *addr)
{
//计算用户释放的内存块所在地址：用户使用地址 - 块头大小
mm_heap_s *p_curr = addr - sizeof(mm_heap_s);
//最终合并的内存块
mm_heap_s *p_result = p_curr;
//整个堆内存的起始地址
void *addr_min = (void*) &mm_heap[0];
//整个堆内存的结束地址
void *addr_max = (void*) &mm_heap[MM_SIZE_HEAP];
//后继内存块地址
void *addr_next = (void *) p_curr + sizeof(mm_heap_s) + p_curr->size + sizeof(void*);
//前驱内存块地址（注意，这里是与当前内存志相邻的最后4字节指针地址，不是前驱内存块的地址）
void *addr_pre = (void*) p_curr - sizeof(void *);
//如果前驱内存块与后继内存块都是有效的
if (addr_pre >= addr_min && addr_next < addr_max)
{
//得到后继内存块
mm_heap_s* p_next = (mm_heap_s *) addr_next;
//得到前驱内存块
mm_heap_s* p_pre = *(mm_heap_s **) addr_pre;
//如果前驱内存块和后继内存块都是空闲块
if (!p_next->use_flag && !p_pre->use_flag)
{
//将当前块和其相邻的前驱块和后继块合并为一个新块
p_result = mm_merge_both(p_pre, p_curr, p_next);
//跳转到释放成功标签
goto _free_success;
}
}
//如果后继块地址有效
if (addr_next < addr_max)
{
//得到后续内存块
mm_heap_s* p_next = (mm_heap_s *) addr_next;
//如果后继块是一个空闲块（前驱块不是空闲块）
if (!p_next->use_flag)
{
//将当前块与后继块合并为一个新块
p_result = mm_merge_next(p_curr, p_next);
//跳转到释放成功标签
goto _free_success;
}
}
//如果前驱块地址有效
if (addr_pre >= addr_min)
{
//得到前驱内存块
mm_heap_s* p_pre = *(mm_heap_s **) addr_pre;
//如果前驱块是一个空闲块（后继块不是空闲块）
if (!p_pre->use_flag)
{
//将当前块与后继块合并为一个新块
p_result = mm_merge_pre(p_pre, p_curr);
//跳转到释放成功标签
goto _free_success;
}
}
//如果前驱地址有效
if (addr_pre >= addr_min)
{
//得到前驱内存块的实际地址
mm_heap_s* p_pre = *(mm_heap_s **) addr_pre;
addr_pre = p_pre;
}
//如果前驱地址无效，则设置其为空
else
{
addr_pre = NULL;
}
//如果后继地址有效
if (addr_next < addr_max)
{
//得到后继内存志的实地地址
mm_heap_s* p_next = (mm_heap_s *) addr_next;
addr_next = p_next;
}
//如果后继地址无效，则设置其为空
else
{
addr_next = NULL;
}
//将一个内存块不相邻的前一个空闲块和后一个空闲块用双向指针连接在一起
p_result = mm_link_both_addr(p_curr, addr_pre, addr_next);
//释放内存成功
_free_success: ;
//设置最终新内存块为未使用
p_result->use_flag = 0;
//设置当前块的自身指针
mm_set_self(p_result);
//更新游标
p_cursor = p_result;
}
三、内存越界
大多数操作系统采用了信任程序员原则，也就是说，操作系统认为程序员在申请内存后可以正确的使用这部分内存，并出于安全考虑不会越界使用内存；释放内存时也会释放一个正确的已申请且未释放的内存。这样操作系统在申请和释放内存时就可以节约掉大部分检查时间，这对用户申请和释放内存无疑是划算的，因为用户在申请和释放内存时需要操作系统以最快的速度完成请求。当然，由于操作系统并不会验证用户使用内存的范围和权限，因此当用户使用内存时如果出现内存越界，则会使整个用户程序和操作系统执行异常甚至崩溃（这里我们所说的操作系统是基于Cortex-M3架构的嵌入式操作系统，而非Intel架构的个人电脑操作系统）。
Copyright © 2015-2023 问渠网 辽ICP备15013245号