动态记忆体分配

先备知识: Linker Script 的撰写技巧

撰写 Linker Script 可以让编译器在连结的阶段按照我们的想法将每个 Section 放到指令的记忆体位址上。

以上图为例，系统程序在执行时会将每个区段放到记忆体当中，至於到底要分配哪些区段，每个区段的属性 (可读可写可执行) 就需要使用 Linker Script 来告诉编译器了!

语法教学: 入口点与架构

看到本专案的 os.ld，即为 mini-riscv-os 的 Linker Script:

OUTPUT_ARCH( "riscv" )

ENTRY( _start )

MEMORY
{
  ram   (wxa!ri) : ORIGIN = 0x80000000, LENGTH = 128M
}

观察上面的脚本，可以归纳出几个小结论:

• 输出的执行档会执行在 riscv 平台
• 程序的进入点为 _start
• 该记忆体名称为 ram，其属性为:
  • [x] W (可写)
  • [x] X (可执行)
  • [x] A (可分配)
  • [ ] R (唯读)
  • [ ] I (初始化)
• 记忆体的起点为 0x80000000，长度为 128 MB，换言之，记忆体范围为: 0x08000000 - 0x88000000。

接着，可以看到 Linker Script 在 SECTION 段之中切割了好几的区段，分别是:

• .text
• .rodata
• .data
• .bss

以其中一段的范例对脚本进行解说:

.text : {
    PROVIDE(_text_start = .);
    *(.text.init) *(.text .text.*)
    PROVIDE(_text_end = .);
  } >ram AT>ram :text

• PROVIDE 可以帮助我们定义符号，这些符号也都代表着一个记忆体位址

• *(.text.init) *(.text .text.*) 帮助我们配对任何的 object file 中的 .text 区段。

• >ram AT>ram :text

  • ram 为 VMA (Virtual Memory Address)，当程序运作时，section 会得到这个记忆体位址。
  • ram :text 为 LMA (Load Memory Address)，当该区段被载入时，会被放到这个记忆体位址。

  最後，Linker Script 还定义了起始与终点的 Symbol 以及 Heap 的位置:

  PROVIDE(_memory_start = ORIGIN(ram));
  PROVIDE(_memory_end = ORIGIN(ram) + LENGTH(ram));
  
  PROVIDE(_heap_start = _bss_end);
  PROVIDE(_heap_size = _memory_end - _heap_start);
  

如果用图片表示，记忆体的分布状况如下:

进入正题

Heap 是什麽?

本文中所提到的 Heap 与资料结构的 Heap 不同，这边的 Heap 是指可供作业系统与 Process 分配的记忆体空间，我们都知道，Stack 会存放已经初始化的固定长度资料，比起 Stack，Heap 有了更多弹性，我们想要使用多少空间就分配多少空间，并且在使用後可以进行记忆体回收避免浪费。

#include <stdlib.h>
int *p = (int*) malloc(sizeof(int));
// ...
free(p);

上面的 C 语言范例便是使用 malloc() 进行动态记忆体的配置，并且在使用完毕後呼叫 free() 对记忆体进行回收。

mini-riscv-os 的实作

了解 Heap 与 Linker Script 所描述出的记忆体结构後，就要进入本文的重点了!
在这次的单元中，我们特别切割出一段空间供 Heap 使用，这样一来，在系统程序中也可以实现类似於 Memory Allocator 的功能:

.section .rodata
.global HEAP_START
HEAP_START: .word _heap_start

.global HEAP_SIZE
HEAP_SIZE: .word _heap_size

.global TEXT_START
TEXT_START: .word _text_start

.global TEXT_END
TEXT_END: .word _text_end

.global DATA_START
DATA_START: .word _data_start

.global DATA_END
DATA_END: .word _data_end

.global RODATA_START
RODATA_START: .word _rodata_start

.global RODATA_END
RODATA_END: .word _rodata_end

.global BSS_START
BSS_START: .word _bss_start

.global BSS_END
BSS_END: .word _bss_end

在 mem.s 中，我们宣告多个变数，每个变数都代表了先前在 Linker Script 定义的 Symbol，这样一来，我们就可以在 C 程序中取用这些记忆体位址:

extern uint32_t TEXT_START;
extern uint32_t TEXT_END;
extern uint32_t DATA_START;
extern uint32_t DATA_END;
extern uint32_t RODATA_START;
extern uint32_t RODATA_END;
extern uint32_t BSS_START;
extern uint32_t BSS_END;
extern uint32_t HEAP_START;
extern uint32_t HEAP_SIZE;

如何管理记忆体区块

其实在主流的作业系统中，Heap 的结构非常复杂，会有多个列表管理未被分配的记忆体区块以及不同大小的已分配记忆体区块。

static uint32_t _alloc_start = 0;
static uint32_t _alloc_end = 0;
static uint32_t _num_pages = 0;

#define PAGE_SIZE 256
#define PAGE_ORDER 8

在 mini-riscv-os 中，我们统一区块的大小为 25b Bits，也就是说，当我们呼叫 malloc(sizeof(int)) 时，他也会一口气分配 256 Bits 的空间给这个请求。

void page_init()
{
  _num_pages = (HEAP_SIZE / PAGE_SIZE) - 2048;
  lib_printf("HEAP_START = %x, HEAP_SIZE = %x, num of pages = %d\n", HEAP_START, HEAP_SIZE, _num_pages);

  struct Page *page = (struct Page *)HEAP_START;
  for (int i = 0; i < _num_pages; i++)
  {
    _clear(page);
    page++;
  }

  _alloc_start = _align_page(HEAP_START + 2048 * PAGE_SIZE);
  _alloc_end = _alloc_start + (PAGE_SIZE * _num_pages);

  lib_printf("TEXT:   0x%x -> 0x%x\n", TEXT_START, TEXT_END);
  lib_printf("RODATA: 0x%x -> 0x%x\n", RODATA_START, RODATA_END);
  lib_printf("DATA:   0x%x -> 0x%x\n", DATA_START, DATA_END);
  lib_printf("BSS:    0x%x -> 0x%x\n", BSS_START, BSS_END);
  lib_printf("HEAP:   0x%x -> 0x%x\n", _alloc_start, _alloc_end);
}

在 page_init() 当中可以看到，假设有 N 个 256 Bits 的记忆体区块可供分配，我们势必要实作出一个资料结构来管理记忆体区块的状态:

struct Page
{
  uint8_t flags;
};

因此，Heap 的记忆体会被用来存放: N 个 Page Struct 以及 N 个 256 Bits 的记忆体区块，呈现一对一的关系。
至於，要如何分辨第 A 个记忆体区块是否被分配，就要看与之对应的 Page Struct 中的 flag 记录了什麽:

• 00: This means this page hasn't been allocated
• 01: This means this page was allocated
• 11: This means this page was allocated and is the last page of the memory block allocated

00 与 01 的状态十分易懂，至於 11 会在哪种情况用到呢?我们继续往下看:

void *malloc(size_t size)
{
  int npages = pageNum(size);
  int found = 0;
  struct Page *page_i = (struct Page *)HEAP_START;
  for (int i = 0; i < (_num_pages - npages); i++)
  {
    if (_is_free(page_i))
    {
      found = 1;

      /*
			 * meet a free page, continue to check if following
			 * (npages - 1) pages are also unallocated.
			 */

      struct Page *page_j = page_i;
      for (int j = i; j < (i + npages); j++)
      {
        if (!_is_free(page_j))
        {
          found = 0;
          break;
        }
        page_j++;
      }
      /*
			 * get a memory block which is good enough for us,
			 * take housekeeping, then return the actual start
			 * address of the first page of this memory block
			 */
      if (found)
      {
        struct Page *page_k = page_i;
        for (int k = i; k < (i + npages); k++)
        {
          _set_flag(page_k, PAGE_TAKEN);
          page_k++;
        }
        page_k--;
        _set_flag(page_k, PAGE_LAST);
        return (void *)(_alloc_start + i * PAGE_SIZE);
      }
    }
    page_i++;
  }
  return NULL;
}

透过阅读 malloc() 的原始码可以得知，当使用者里用它尝试获取大於 256 Bits 的记忆体空间时，他会先计算请求的记忆体大小需要多少区块才能满足。计算完成後，他会在连续的记忆体区块中寻找相连且未分配的记忆体区块分配给该请求:

malloc(513);
Cause 513 Bits > The size of the 2 blocks,
thus, malloc will allocates 3 blocks for the request.

Before Allocation:

+----+    +----+    +----+    +----+    +----+
| 00 | -> | 00 | -> | 00 | -> | 00 | -> | 00 |
+----+    +----+    +----+    +----+    +----+

After Allocation:

+----+    +----+    +----+    +----+    +----+
| 01 | -> | 01 | -> | 11 | -> | 00 | -> | 00 |
+----+    +----+    +----+    +----+    +----+

分配完成後，我们可以发现最後一个被分配的记忆体区块的 Flag 为 11，这样一来，等到使用者呼叫 free() 释放这块记忆体时，系统就可以透过 Flag 确认带有 11 标记的区块是需要被释放的最後一块区块。

Reference

• 10 分钟读懂 linker scripts
• Step by step, learn to develop an operating system on RISC-V
• Heap Exploitation