Custom Memory Allocator

发表于 分类于 阅读次数： 本文字数： 2.1k 阅读时长 ≈ 4 分钟

如何实现一个简单内存分配

具体代码可以参考我这里实现的简单动态内存分配
这里仅仅只是实现了的内存的分配，之后还需要实现内存池，并且通过栈的方式进行管理才能方便使用。

在实现这个问题之前，我们需要了解一下程序中的内存布局。

  • text
    存放要由处理器执行的二进制指令的部分。
  • data、
    存放非零初始化的静态数据
  • bss
    存放初始化为零的静态数据，并且未初始化的静态数据被初始化为零后将合并到这个区域
  • heap
    这里主要是动态分配的数据，也叫堆
  • stack
    这里是局部变量等非动态分配的数据，也叫栈

MemoryLayout

可以看到堆和栈的增长方式是相对生长

开始有个一个指针叫做program break或者brk,他是与bss重合的,当开始分配的内存，brk会上升，其中增大的内存空间为heap。

所以当我们需要动态分配空间的时候，需要请求系统，系统内部接口会帮助我们增大brk指针

相反，当我们需要释放空间的时候，也需要请求系统，系统内部接口会帮助我们减小brk指针

如何操控brk指针

本文使用的是linux操作系统。系统接口函数为 sbrk()
当然也可以使用 brk() 这个系统调用。

具体使用方法可以通过命令 man sbrk 来查看。

1
2
3
sbrk(0); // 获取当前brk指针
sbrk(n); // 分配大小为n个字节的内存空间, brk指针增大n个字节, 返回分配的起始地址
sbrk(-n); // 释放大小为n个字节的内存空间, brk指针减小n个字节, 返回分配的起始地址

申请或者释放total_size个字节空间

1
2
3
4
5
6
void *now_addr = sbrk(total_size);
if (now_addr == (void *)-1) { 
  // failed
  printf("%s errno: %s\n", __func__, strerror(errno));
  return nullptr;
}

由于每次分配内存返回的是其实地址, 考虑到释放问题, 我们每次分配都需要添加一个头结构体, 用来保存一下用户需要分配的内存大小, 以及进行填充来实现内存对齐。

添加头部分

我这里实现的是对齐16个字节

1
2
3
4
5
6
7
8
9
10
11
12
// 16 位对齐
const unsigned align_to = 16;
typedef char ALIGN[align_to];
// 标头
typedef union header {
  struct {
    size_t size;
    union header *pre;
    union header *next;
  } head;
  ALIGN align;
} header_t;

其实这里可以化简, 不需要指向下一个以及上一个被分配的空间的指针

1
2
3
4
5
6
7
8
9
10
11
// 16 位对齐
const unsigned align_to = 16;
typedef char ALIGN[align_to];
// 标头
typedef union header {
  struct {
    size_t size;
  } head;
  ALIGN align;
} header_t;

MemoryMalloc

关于内存对齐问题

我们调用sbrk分配空间的时候, 为了提高Cpu读取的效率, 我们需要进行内存对齐

例如 我们的Cpu每次读取16个字节
如果 分配的内存是16的n倍, 那么只需要读取n次即可
但是如果不是, 那么就会读取超过n次

1
2
3
4
5
6
7
8
9
10
11
12
假设XXXX为其他数据, OOOO为我们分配的数据
分配同样大小的空间

Cpu 读取  -> XXXX XXXX XXXX XXXX 
Cpu 读取  -> OOOO OOOO OOOO OOOO
Cpu 读取  -> XXXX XXXX XXXX XXXX
如上排列, Cpu只需要读1次, 就可以获取我们分配的空间

Cpu 读取  -> XXXX XXXX XXXX OOOO  
Cpu 读取  -> OOOO OOOO OOOO XXXX
Cpu 读取  -> XXXX XXXX XXXX XXXX
这样排列, Cpu就需要读2次

这就是内存对齐的好处

1
2
// 如果要分配size个字节, 那么实际要分配total_size个字节
size_t total_size = (sizeof(header_t) + size + align_to - 1) & ~(align_to - 1);

其实就是使得每次分配的内存空间(包含头以及填充), 使得为16的整数倍

malloc核心代码

1
2
3
4
5
6
7
// malloc memory space
void *now_addr = sbrk(total_size);
  // failed
if (now_addr == (void *)-1) {
  printf("%s errno: %s\n", __func__, strerror(errno));
  return nullptr;
}

free核心代码

1
2
3
4
5
6
// free memory space
if (sbrk(0 - (sizeof(header_t) + node->head.size)) == (void *)-1) {
  printf("%s errno: %s\n", __func__, strerror(ENOMEM));
  pthrad_mutex_unlock(&list_locker);
return;
}