如何计算堆的大小,只有算出可用空间才能对其管理。

ENTRY

功能:用于设置入口点,即程序中执行的第一条指令 symbol 参数是一个符号的名称

OUTPUT_ARCH

功能:指定输出文件所适用的计算机体系架构

为什么用 riscv64-unknown-elf-gcc,但是编译出来的文件是 32 位程序? riscv64 是 host 是 64 位系统,编译 target 是由 gcc 的参数决定

MEMORY

功能:用于描述目标机器上内存区域的位置,大小和相关

MEMORY
{
    /* 内存类型为ROM,起始地址0,长度256K */
    rom(rx):ORIGIN = 0, LENGTH = 256K
    /* 内存类型为RAM,起始地址0x40000000,长度4M */
    ram(!rx):org = 0x40000000, l = 4M
}

TODO:括号里的 rx 含义是?

SECTION

功能:告诉链接器如何将 input sections 映射到 output sections,以及如何将 output sections 放置到内存中。

SECTION
{
    .=0x0000;
    .text:{*(.text)}
    .=0x8000000;
    .data:{*(.data)}
    .bss:{*(.bss)}
}>ram

PROVIDE

功能:

  • 可以在 Linker Script 中定义符号(Symbols)
  • 每个符号包括一个名字(name) 和一个对应的地址值(address)
  • 在代码中可以访问这些符号,等同于访问一个地址。
 .bss :{
  PROVIDE(_bss_start = .);    /* 当前地址赋值给符号_bss_start */
  *(.sbss .sbss.*)
  *(.bss .bss.*)
  *(COMMON)
  PROVIDE(_bss_end = .);
 } >ram
    PROVIDE(_memory_start = ORIGIN(ram));
 PROVIDE(_memory_end = ORIGIN(ram) + LENGTH(ram));

 PROVIDE(_heap_start = _bss_end); /* 堆空间就是接在了bss段之后,所以堆开始地址就是bss结束地址 */ 
 PROVIDE(_heap_size = _memory_end - _heap_start); /* 计算堆大小 */ 

.global表示全局变量,.word表示定义变量,下面的代码就是定义一些全局变量,方便在 C 代码中使用。

/* mem.S */ 
.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
/*
 * Following global vars are defined in mem.S
 */
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;

#define PAGE_SIZE 4096
static uint32_t _num_pages = _num_pages = (HEAP_SIZE / PAGE_SIZE) - 8;

实现 Page 级别的内存分配与释放

日常使用的操作系统,都是以字节为单位分配空间,但是为了教学方便,RVOS 是以 Page 为单位分配内存。

数据结构设计

数组方式管理

将内存模拟为一个连续的数组,数组的前部预留 8 个 Page 来管理其余的内存。目前考虑管理的状态有:

  • 这 Page 是否被使用了
  • 这个 Page 是不是最后一块分配的内存,方便我们释放内存时找到最后一块分配的内存

我们可以使用一个 8 bit 的flag来记录这些信息,flag bit[0]表示是否已使用,flag bit[1]表示是否是最后一个分配的页面。

/*
 * Page Descriptor 
 * flags:
 * - bit 0: flag if this page is taken(allocated)
 * - bit 1: flag if this page is the last page of the memory block allocated
 */
struct Page {
 uint8_t flags;
};

也就是每一个 Page 都由一个 8 bit 的结构体struct Page管理,我们总共分配了 8 个 Page 用来管理,一个 Page 占 4K,那么我们可以一个管理$8 \times 4096 = 32768$个 Page。那就刚好可以管理$32768 \times 4096 = 134217728 \text{bit}$内存=128M。

Responsive Image

Page 分配与释放接口设计

/*
 * 分配连续n个可用物理页
 * - npages: 需要分配的页的个数
 */
void *page_alloc(int npages)
{
 /* Note we are searching the page descriptor bitmaps. */
 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;
   /* 
    * 找到第一个可用Page,继续判断是否有N个连续可用page
    */
   struct Page *page_j = page_i;
   for (int j = i; j < (i + npages); j++) {
    if (!_is_free(page_j)) {
     found = 0;
     break;
    }
    page_j++;
   }
   /*
    * 找到了连续的N个可用page,将N个page设置为已分配状态
    */
   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);
                // 返回可用page首地址
    return (void *)(_alloc_start + i * PAGE_SIZE);
   }
  }
  page_i++;
 }
 return NULL;
}
/*
 * 释放已分配的物理页
 * - p: 待释放的首地址
 */
void page_free(void *p)
{
 /*
  * 判断非法输入,p不能为空或者超出最大可分配大小
  */
 if (!p || (uint32_t)p >= _alloc_end) {
  return;
 }
 /* 计算出这个首地址p所在的page的描述符,也就是找到第几个描述符在管理这块内存 */
 struct Page *page = (struct Page *)HEAP_START;
 page += ((uint32_t)p - _alloc_start)/ PAGE_SIZE;
 /* 循环清空标识 */
 while (!_is_free(page)) {
  if (_is_last(page)) {
   _clear(page);
   break;
  } else {
   _clear(page);
   page++;;
  }
 }
}