前言

jyy老师太强了。这一章介绍一下并发控制中互斥相关的内容，并实现课程中的L1实验

互斥

实现共享内存上的互斥，并不是一个非常简单的事情:

  1. 系统不能同时读/写共享内存(除了原子指令)，即load时不能写，只能单纯的读;而写的时候，无法进行读(即使类似于addq $1, [sum]这种指令，其也是分为读值、计算和写值三部分)。从而当一个线程完成状态读取和状态设置时，其实这两者之间可能状态已经发生了变化(另一个线程完成了状态读取和状态设置)
  2. 系统可能乱序执行指令。可能有些精妙的算法可以规避1.中的问题，例如Peterson算法。但是现代操作系统可能的指令乱序执行(即可能在读之前完成写)，也会导致互斥的失败

可以看到，单纯的从软件上实现共享内存的互斥是非常困难的一件事情，因此这就往往需要硬件上进行协调配合!
硬件可以通过诸如锁总线的方式，原子的实现load-exec-store指令，从而为我们实现共享内存上的互斥提供了有效的解决方法。
这些原子指令，完美的解决了上面的两个难点，因此很容易就实现共享内存的互斥。这些方案往往简洁，且很好理解，如下面基于xchg的自选锁实现的共享内存的互斥。

1
2
3
4
5
6
7
8
9
int locked = 0;

void lock() {
	while(xchg(&locked, 1));
}

void unlock() {
	xchg(&locked, 0);
}

可以看到，由于xchg是原子的，因此任何时候，永远只可能有一个线程，在执行lock或unlock中的xchg指令，而只要有线程成功获取了锁(xchg返回的值为0)，则其同时会将locked的值设置为1，直到其归还锁之前，不会再有其他人获取锁。因此其简洁的实现了共享内存的互斥

L1物理内存管理(pmm)

实验背景

从这次实验开始，我们将真正的开始实现一个操作系统。
在实现操作系统内核时，经常会需要为操作系统中新增的对象分配存储空间。在这些对象不再使用时，有需要将这些对象的内存进行回收。例如在前面的M2中调用co_start分配协程结构体资源;调用co_wait回收上述分配的资源。
当然，对于迷你自制的操作系统来说，每种类型的资源都进行手工分配和释放是完全可行的。但是实现内存的自动分配和释放，可以简化操作系统内核中很多部分的代码，是十分值得的。
在本次实验中，需要亲自体验平常使用的malloc/free应该如何实现。在多处理器系统中，各个处理器上的代码会并发地申请或释放内存，这会给内存分配和释放带来额外的挑战——一方面，希望不同处理器可以并行、高效地申请内存，少量甚至不会出现同时申请而产生一个处理器等待另一个处理器的情况;另一方面，不希望malloc/free仅仅通过简单粗暴使用一把互斥锁来保护，从而降低了内存管理的效率

实验描述

实验要求1:实现多处理器安全的内存分配和回收

类似于malloc/free，在bare-metal上实现内存分配/回收的函数:

1
2
3
4
5
6
7
static void *kalloc(size_t size) {
//内存分配
}

static void *kfree(void *ptr) {
//内存释放
}

在AbstractMachine启动后，$[heap.start, heap.end]$都是可用的物理内存(堆区)，kalloc返回的内存必须位于这个区间中。具体来说这个实验中你需要实现一个数据结构，维护一个不相交区间的集合(堆区)

初始时，堆区为空。假设当前堆区为$H$，$heap.start = L，heap.end = R$

  • `kalloc(s)分配s字节的内存$[\mathcal{l}, \mathcal{r})$满足
    分配发生在堆区中
    分配的内存不与已分配内存重叠()
    得到新的堆区并返回新分配区间的左端点$\mathcal{l}$
  • `kfree($\mathcal{l}$)删除一个已有区间$[\mathcal{l}, \mathcal{r}) \in H$，得到新的堆区当$\mathcal{l}$不是$H$中任何一个区间左端点时，产生undefined behavior

除了上面的抽象描述，还有一些作为计算机系统软件基础设施的要求:

  • 对于大小为$s$的内存分配请求，返回的内存地址必须对齐到$2^{i}$，其中$i$是最小的满足$2^{i} \ge s$。例如，分配17字节内存返回的地址必须是32的整数倍
  • 在分配算法不能找到足够的内存继续分配时，返回NULL(0)
    • 受分配算法的局限，可能系统中仍然有空闲的内存，但形成了碎片的内存，或者单纯是分配算法不能找到这些内存而导致失败，这是允许的。
  • 由于这些API仅仅在自制的操作系统内核中使用，可以直接拒绝超过16MB的内存分配
  • 不必初始化返回的内存，当然，对返回的内存赋上初始值是个不错的主意
  • 最重要的要求在于允许多处理器并行地调用kalloc/kfree:
    • 不同的处理器可能同时执行kalloc分配大小不同的内存
    • 不同的处理器可能同时执行kfree释放内存
    • 在一个处理器分配的内存，可能在另一个处理器上释放
    • 在kalloc/kfree实现正确的前提下，尽可能使不同处理器上的内存分配能够并行

实验要求2:实现AbstractMachine中缺失的函数

在L0中，已经提出了这个实验要求。从现在开始，正式建议实现klib里缺失的函数——没有printf、sprintf等函数，根本就是在使用汇编语言写操作系统

实验指南

代码组织与运行

实验框架代码由三个目录组成:

1
2
3
4
5
6
7
8
9
10
.
+--framework	->	框架代码;	可以在本地修改
|	+--kernel.h
|	+--main.c
+--include	->	头文件;	可以自由修改/创建文件
|	+--common.h
+--Makefile
+--src		->	源文件; 可以自由修改/创建文件
    +--os.c
    +--pmm.c

可以使用前面提到的技巧(即执行make -nB | sed "s/^/\n/g" | sed "s/ /\n\t/g"，观察并了解整个系统镜像的生成过程:

  1. 首先，其编译相关的源文件,生成目标文件，样例如下所示
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    x86_64-linux-gnu-gcc
            -std=gnu11
            -O2
            -MMD
            -Wall
            -Werror
            -ggdb
            -Iinclude/
            -Iframework/
            -I/home/hawk/Desktop/nju/kernel/include
            -I/home/hawk/Desktop/nju/kernel/../abstract-machine/am/include/
            -I/home/hawk/Desktop/nju/kernel/../abstract-machine/klib/include/
            -D__ISA__=\"x86_64\"
            -D__ISA_X86_64__
            -D__ARCH__=x86_64-qemu
            -D__ARCH_X86_64_QEMU
            -D__PLATFORM__=qemu
            -D__PLATFORM_QEMU
            -DARCH_H=\"arch/x86_64-qemu.h\"
            -fno-asynchronous-unwind-tables
            -fno-builtin
            -fno-stack-protector
            -Wno-main
            -m64
            -fPIC
            -mno-sse
            -c
            -o
            /home/hawk/Desktop/nju/kernel/build/x86_64-qemu/framework/main.o
            /home/hawk/Desktop/nju/kernel/framework/main.c
  2. 链接生成ELF文件，命令如下
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    x86_64-linux-gnu-ld
            -melf_x86_64
            -N
            -Ttext-segment=0x00100000
            -o
            /home/hawk/Desktop/nju/kernel/build/kernel-x86_64-qemu.elf
            /home/hawk/Desktop/nju/kernel/build/x86_64-qemu/framework/main.o
            /home/hawk/Desktop/nju/kernel/build/x86_64-qemu/./src/pmm.o
            /home/hawk/Desktop/nju/kernel/build/x86_64-qemu/./src/os.o
            /home/hawk/Desktop/nju/kernel/../abstract-machine/am/build/am-x86_64-qemu.a
            /home/hawk/Desktop/nju/kernel/../abstract-machine/klib/build/klib-x86_64-qemu.a

  3. 最后，生成可以运行的磁盘镜像文件，其命令如下所示

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    (
            cat
            /home/hawk/Desktop/nju/kernel/../abstract-machine/am/src/x86/qemu/boot/bootblock.o;
            head
            -c
            1024
            /dev/zero;
            cat
            /home/hawk/Desktop/nju/kernel/build/kernel-x86_64-qemu.elf
            )
            >
            /home/hawk/Desktop/nju/kernel/build/kernel-x86_64-qemu

    如果想要运行的话，和之前L0的实验是类似的，使用make即可执行，指令如下所示

    1
    make run ARCH=x86_64-qemu

    如果要启动多个处理器，则传递smp环境变量即可，执行如下命令即可启动4各处理器

    1
    make run ARCH=x86_64-qemu smp = 4

框架代码导读

框架代码很短，其从main函数首先执行os的初始化，然后启动多个处理器，每个处理器都跳转到os->run执行

1
2
3
4
5
int main() {
  os->init();
  mpe_init(os->run);
  return 1;
}

os是一个操作系统的模块，可以看成是使用C实现的面向对象的编程，可曾强代码的可读性。其主要借助于下面的宏，实现模块的声明和定义

1
2
3
4
5
6
7
8
9
#define MODULE(mod) \
  typedef struct mod_##mod##_t mod_##mod##_t; \
  extern mod_##mod##_t *mod; \
  struct mod_##mod##_t

#define MODULE_DEF(mod) \
  extern mod_##mod##_t __##mod##_obj; \
  mod_##mod##_t *mod = &__##mod##_obj; \
  mod_##mod##_t __##mod##_obj

上面MODULE用来声明一个模块，而使用MODULE_DEF来真正的定义这个模块。当然，这样子的视觉效果不是很好，可以将前面相关的编译命令中的-c参数更换为-E，其有如下形式的代码

1
2
3
4
5
6
7
8
9
10
typedef struct mod_os_t mod_os_t; extern mod_os_t *os; struct mod_os_t {
  void (*init)();
  void (*run)();
};


extern mod_os_t __os_obj; mod_os_t *os = &__os_obj; mod_os_t __os_obj = {
  .init = os_init,
  .run = os_run,
};

实际上想要读懂这份宏，需要弄明白二点:

  1. 宏是字面替换，MODULE(mod)中所有的mod都会被替换掉
  2. ##是C语言用来拼接标识符的机制，sys ## tem，可以得到system

框架代码的运行

在当前的操作系统内核中，目前只有两个函数

  • os->init()，其完成操作系统所有部分的初始化。os_init()运行在系统启动后的第一个处理器上，中断处于关闭状态;此时系统中的其他处理器尚未被启动
  • os->run()是所有处理器的入口，在初始化完成后，框架代码调用mpe_init(os->run)，启动所有处理器执行。原始框架代码中，os->run只是打印Hello World之后就开始死循环;你之后可以在os->run中添加各种测试代码

实现kalloc/kfree

相关的实现主要在pmm(physical memory management)模块:

1
2
3
4
5
MODULE(pmm) {
	void (*init)();
	void *(alloc)(size_t size);
	void (*free)(void *ptr);
}

该模块共包含三个函数指针:

  • pmm->init()初始化pmm模块，其应该在多处理器启动前，即os->init()中调用。这里应该实现数据结构、锁的初始化等
  • pmm->alloc()，即对应实验要求中的kalloc
  • pmm->free()，即对应实验要求中的kfree

测试/调试代码

构建测试框架

AbstractMachine代码的调试是比较困难的——无论是native，亦或是在qemu模拟器中。因此，同构构建一个测试框架，对于定位bug是非常有用的
下面以调用thread.h中API为例，构建一个测试代码框架
首先创建一个test目录，用于存放和测试相关的代码，如下所示

1
2
3
4
5
test
  +——am.h			一个空的am.h
  +——common.h
  +——test.c
  +——threads.h			前面课程中给出的pthread包装API

为了修改最少的代码，并且能够兼容已有的项目，可以在pmm.c文件中，增加一些条件编译，如下所示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#ifndef TEST
// 框架代码中的 pmm_init (在 AbstractMachine 中运行)
static void pmm_init() {
  uintptr_t pmsize = ((uintptr_t)heap.end - (uintptr_t)heap.start);
  printf("Got %d MiB heap: [%p, %p)\n", pmsize >> 20, heap.start, heap.end);
}
#else
// 测试代码的 pmm_init ()
static void pmm_init() {
  char *ptr  = malloc(HEAP_SIZE);
  heap.start = ptr;
  heap.end   = ptr + HEAP_SIZE;
  printf("Got %d MiB heap: [%p, %p)\n", HEAP_SIZE >> 20, heap.start, heap.end);
}
#endif

接着在对应的Makefile文件中，增加一个编译目标

1
2
3
4
5
6
test: git
        @gcc $(shell find src/ -name "*.c")  \
             $(shell find test/ -name "*.c") \
             -Iframework -Itest -DTEST -lpthread \
             -o build/test
        @build/test

设计测试用例

为了确保代码在各种场合下，都可以正常的运行，需要尝试各种类型下的极端测试。此时，可以简单的利用前面构建的代码框架，批量地运行很多测试，如下所示

1
2
3
4
5
6
7
8
int main(int argc, char *argv[]) {
  if (argc < 2) exit(1);
  switch(atoi(argv[1])) {
    case 0: do_test_0();
    case 1: do_test_1();
    ...
  }
}

然后在Makefile里批量地进行运行，如下所示

1
2
3
4
5
testall: test
        @build/test 0
        @build/test 1
        @build/test 2
        ...

性能调优

此时需要选取适当的workload进行调优，并且确定程序的性能瓶颈。理解程序性能的最好方法是使用正确的工具:profiler。作为本地进程运行的测试用例，其可以使用Linux系统自带的各种工具，快速的判断程序的性能瓶颈

实验环境

类似的，切换到master分支，然后从github上拉取L1实验即可

1
git remote add jyy https://hub.fastgit.org/NJU-ProjectN/os-workbench.git && git checkout master && git pull jyy L1

实验实现

下面是个人的思路及其实现，实验实现

测试框架

虽然按照实验指南的说明，对于多处理器的AbstractMachine来说，无论是在native亦或是QEMU模拟器中，由于AM APIs都和系统有紧密的耦合，因此调试起来并不是很方便。但实际上并非如此——在gdb中，无论是在QEMU模拟器中、亦或是native中，多处理器中的每一个处理器都相当于一个线程，因此使用gdb中调试多线程的方式来调试AbstractMachine代码即可
不妨以QEMU模拟器为例，我们执行如下命令启动多处理器的AbstractMachine，其中smp参数指定多处理器数量

1
$(QEMU) -gdb tcp::1737 -S -serial stdio -smp $(smp) -drive format=raw,file=./build/kernel-$(ARCH) -no-reboot -no-shutdown

然后在终端启动gdb，调试QEMU远程开启的远程gdb服务器，执行如下命令即可

1
gdb -ex "target remote localhost:1737" -ex "dir ./src" ./build/kernel-x86_64-qemu.elf

如果此时想要查看多处理器的处理器信息，并切换到指定的处理器上，则在gdb中执行如下调试多线程的命令进行查看

1
2
(gdb) info threads
(gdb) thread [threadId]

可以看到，实际上调试多处理器的AbstractMachine并不是很困难。虽然如此，由于本次实验对于不同的workload的性能和准确性都有一定要求，因此构造一个测试框架，进行自动的编译、运行测试和清理是十分有帮助的。

  1. 添加条件编译

    为了最小程度的修改源代码，并且在任何时候都可以通过make run或make test=pmm,buddy命令，来编译、运行对应的正常样例和测试样例，我们通过添加条件编译来实现。除此之外，为了适应项目的需要，测试kalloc和kfree在不同workload下的正确性和性能，我们使用宏选择测试的函数，这样子对于新的测试样例，只需要增添宏即可

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    //os.c

    #if defined TESTpmm
      static void os_run() {
        printf("test the pmm\n");
        test_pmm();
      }
    #else
      static void os_run() {

        printf("Hello World from CPU #%d\n", cpu_current());
        while (1) {;}
      }
    #endif
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    //pmm.c

    #if defined TESTbuddy
      //测试buddys方式
      void test_pmm() {
        int size = 0;
        #define CAPACITY (500)
        char *array[CAPACITY] = {NULL};
        int array_size[CAPACITY] = {0};
        while (1) {
          switch (rand() % 2)
          {
            case 0:
              if(size < CAPACITY) {
                array_size[size] = BUDDY_IDX2CHUNK_SIZE(rand() % buddys_size);
                array[size] = (char*)buddys_alloc(array_size[size]);

                if(array[size] != NULL) {
                  printf("cpu%d:buddys_alloc(%X) = %X\n", (int)cpu_current(), (uint64_t)(uintptr_t)array_size[size], (uint64_t)(uintptr_t)array[size]);

                  //填充，方便进行调试
                  for(int i = 0; i < array_size[size]; ++i) { array[size][i] = (char)array_size[size];}
                  ++size;
                }
              }
              break;

            case 1:
              if(size) {
                --size;
                for(int i = 0; i < array_size[size]; ++i) {
                  panic_on(array[size][i] != (char)array_size[size], "corrupted");
                }
                buddys_free((Chunk*)array[size]);
                printf("cpu%d:buddys_free(%X)\n", (int)cpu_current(), (uint64_t)(uintptr_t)array[size]);
              }
              break;
          }
        }
      }
    #elif defined TESTslab
      //测试slabs方式
      void test_pmm() {
        int size = 0;
        #define CAPACITY (500)
        char *array[CAPACITY] = {NULL};
        int array_size[CAPACITY] = {0};
        while (1) {
          switch (rand() % 2)
          {
            case 0:
              if(size < CAPACITY) {
                array_size[size] = SLAB_IDX2CHUNK_SIZE(rand() % slabs_size);
                array[size] = (char*)slabs_alloc(array_size[size]);

                if(array[size] != NULL) {
                  printf("cpu%d:slabs_alloc(%X) = %X\n", (int)cpu_current(), (uint64_t)(uintptr_t)array_size[size], (uint64_t)(uintptr_t)array[size]);

                  //填充，方便进行调试
                  for(int i = 0; i < array_size[size]; ++i) { array[size][i] = (char)array_size[size];}
                  ++size;
                }
              }
              break;

            case 1:
              if(size) {
                --size;
                for(int i = 0; i < array_size[size]; ++i) {
                  panic_on(array[size][i] != (char)array_size[size], "corrupted");
                }
                slabs_free((Chunk*)array[size]);
                printf("cpu%d:slabs_free(%X)\n", (int)cpu_current(), (uint64_t)(uintptr_t)array[size]);
              }
              break;
          }
        }
      }
    #else
      void test_pmm() {
        int size = 0;
        #define CAPACITY (500)
        char *array[CAPACITY] = {NULL};
        int array_size[CAPACITY] = {0};
        int total = 0, counts[3] = {80, 19, 1};
        uintptr_t BOUNDARY1 = 128, BOUNDARY2 = 32 KB, BOUNDARY3 = 1 MB / 2;
        while (1) {
          switch (rand() % 2)
          {
            case 0:
              /*
               * 为了模拟workload,我们通过rand()来模拟申请的大小
               *
               * 我们以每一轮50次一个统计
               * 则大量、频繁的小内存分配/释放；其中绝大部分不超过 BOUNDARY1 字节， 这里默认80%概率为小内存分配，也就是80轮
               * 较为频繁的，以物理页面大小为单位的分配/释放 (4 KiB)；这里默认19%概率分配，也就是19轮，大小不超过BOUNDARY2
               * 非常罕见的大内存分配，即1轮，大小不超过BOUNDARY3
               */
              if(size < CAPACITY) {
                for(int mode = rand() % 3; ; mode = (mode + 1) % 3) {
                  if(counts[mode]) {
                    --counts[mode];
                    switch(mode) {
                      case 0:
                        array_size[size] = 1 + (rand() % BOUNDARY1);
                        break;
                      case 1:
                        array_size[size] = PAGESIZE * (1 + (rand() % (BOUNDARY2 / PAGESIZE)));
                        break;
                      case 2:
                        array_size[size] = BUDDY_IDX2CHUNK_SIZE(BUDDY_CHUNK_SIZE2IDX(BOUNDARY2) + 1 + (rand() % (BUDDY_CHUNK_SIZE2IDX(BOUNDARY3) - BUDDY_CHUNK_SIZE2IDX(BOUNDARY2))));
                        break;
                    }
                    break;
                  }
                }
                if(++total == 100) {
                  total = 0;
                  counts[0] = 80;
                  counts[1] = 19;
                  counts[2] = 1;
                }

                array[size] = (char*)pmm->alloc(array_size[size]);

                panic_on(array[size] == NULL, "not enough space");
                printf("cpu%d:pmm->alloc(%X) = %X\n", (int)cpu_current(), (uint64_t)(uintptr_t)array_size[size], (uint64_t)(uintptr_t)array[size]);

                //填充，方便进行调试
                for(int i = 0; i < array_size[size]; ++i) { array[size][i] = (char)array_size[size];}
                ++size;
              }
              break;

            case 1:
              if(size) {
                --size;
                for(int i = 0; i < array_size[size]; ++i) {
                  panic_on(array[size][i] != (char)array_size[size], "corrupted");
                }
                pmm->free((Chunk*)array[size]);
                printf("cpu%d:pmm->free(%X)\n", (int)cpu_current(), (uint64_t)(uintptr_t)array[size]);
              }
              break;
          }
        }
      }
    #endif

  2. 添加编译目标
    这里为了实现通过make自动编译和执行不同的内核，需要添加编译目标。通过修改kernel目录下的相关Makefile实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    NAME           	:= kernel
    SRCS           	:= framework/main.c $(shell find -L ./src/ -name "*.c")
    INC_PATH       	:= include/ framework/

    export AM_HOME := $(PWD)/../abstract-machine
    ifeq ($(ARCH),)
    export ARCH    	:= x86_64-qemu
    endif

    ifeq ($(ARCH), x86_64-qemu)
    export QEMU		:= qemu-system-x86_64
    else ifeq ($(ARCH), x86-qemu)
    export QEMU 	:= qemu-system-i386
    endif


    ifeq ($(smp),)
    export smp		:= 4
    endif


    COMMA	:=,
    ifneq ($(test),)
    export CFLAGS += $(patsubst %,-DTEST%, $(subst $(COMMA), ,$(test)))
    endif

    ifneq ($(debug),)
    export CFLAGS += $(patsubst %,-DDEBUG%, $(subst $(COMMA), ,$(debug)))
    endif

    ifeq ($(rand),)
    export CFLAGS += -DRANDOM=$(shell date +%N | head -c 6)
    endif

    include $(AM_HOME)/Makefile
    include ../Makefile.lab
    image: git

    gdb: image
    	$(QEMU) -gdb tcp::1737 -S -serial stdio -smp $(smp) -drive format=raw,file=./build/kernel-$(ARCH) -no-reboot -no-shutdown

    其中，关于make相关的内置函数的用法，可以查看手册获取

  3. 运行内核
    如果要运行正常模式下的内核，则只需要设置多处理器个数以及运行环境即可，执行如下样例在本机上模拟四核计算机

    1
    make ARCH=native smp=4 run

    如果要运行制定测试的内核，则指定目标test的值即可，样例如下所示

    1
    make test=pmm,buddy run

实现互斥锁

AbstractMachine文档中给出了原子指令int atomic_xchg(volatile int *addr, int newval)，其会原子地交换内存地址中的数值。
为了方便实现，我们需要包装为两种获取锁(阻塞获取和非阻塞获取)和一种释放所的API，如下所示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//pmm.c
/*
 * 初始化锁
 */
static void
lock_init(int *lock)
{
  atomic_xchg(lock, PMMUNLOCKED);
}


/*
 * 阻塞，直到获取锁
 */
static void
lock_acquire(int *lock)
{
  while(atomic_xchg(lock, PMMLOCKED) == PMMLOCKED) {;}
}


/*
 * 释放获取的锁
 */
static void
lock_release(int *lock)
{
  panic_on(atomic_xchg(lock, PMMUNLOCKED) != PMMLOCKED, "lock is not acquire");
}


/*
 * 其可以用来确认当前是否获取了锁
 * 或者用来非阻塞的获取锁
 */
static int
lock_try_acquire(int *lock)
{
  return atomic_xchg(lock, PMMLOCKED);
}

可以看到，这里实现了一套简易的锁的API

分配对象结构简述

本质上，内存管理是按照一定规则从系统内存上申请内存对象;当释放的时候，再按照一定的规则缓存起来，等待下次申请内存对象时直接使用，而非直接返回给系统，从而提高内存管理的效率和性能。

因此，我们需要根据内存申请的特点，构造对应的内存对象数据结构，从而提高内存管理的效率和安全性。根据前面的实验要求和实验指南:一方面，返回的内存地址必须对齐到$2^{i}$;另一方面，请求的内存大小有如下特征:

  1. 大量、频繁的小内存分配和释放;绝大部分不超过128字节;
  2. 较为频繁的，以物理页面大小为单位的分配/释放(4KiB)
  3. 非常罕见的大内存分配

为了尽可能的高并发，在内存中构建与处理器等数量的内存管理结构，并以循环链表的形式进行管理——每个处理器在申请内存时，会循环遍历这些内存管理结构，找到一个未上锁的内存管理结构，并完成相关的内存申请。
由于其内存地址需要对齐到$2^{i}$，则我们使用伙伴算法;而由于其频繁、大量的进行小内存分配和释放，因此我们使用slab机制缓存所有大小相同的内存对象。
内存数据结构
内存初始布局

申请大小对齐到$2^{i}$

实际上部分CPU提供时间复杂度为$O(1)$的硬件解决方法，但是其没有可移植性。因此我们还是通过二分的软件方法进行实现。
其思路就是通过位运算，其随着位运算的左移个数增加而值减少，是单调的。因此可以通过二分查找，以$O(logn)$的时间复杂度解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/*
 * 计算ceil(log2(n))
 * 0 < n <= 2 ^ (sizeof(uintptr_t) * 8 - 1)
 */
static uintptr_t
log_ceil(uintptr_t n)
{
  panic_on(n <= 0, "log error n");

  if(n == 1) {return 0;}

  uintptr_t left = 0, right = sizeof(uintptr_t) * 8 - 1;


  /*
   * 对于下面的二分法来说
   * 对于所有的n，其计算的是满足2 ^ (a - 1) < n <= 2 * a
   * 在n为2的幂时，会出现错误
   * 则应该首先--n
   */
  --n;
  while(left <= right) {
    uintptr_t middle = left + (right - left) / 2;

    if(n >> middle) { left = middle + 1; }
    else { right = middle - 1; }
  }

  return left;
}

/*
 * 将申请的内存大小向上对齐到最接近的幂
 * 如果小于MINSIZE的内存统一以MINSIZE为主
 * 根据说明，系统中不可能申请超过MAXSIZE大小的内存
 */
static size_t
request_size2mem_size(size_t size)
{
  size = ((size_t)1) << log_ceil(size);

  panic_on(size > MAXSIZE, "size is too big");

  return size < MINSIZE ? MINSIZE : size;
}

内存块信息存储

实际上，对于任意一个内存来说，其除了包含可用的内存地址外，还需要一部分内存，用来保存诸如内存大小等的内存块的信息。
这里由于每次需要对齐，所以类似于ptmalloc2那种的将内存块信息放置在分配的可用内存地址最开始部分是不太可行的。
这里联想到页表机制，从而准备通过类似于bitmap的数组，其每一个元素都代表一片内存的相关属性。

chunks数组

这里最终使用类似于bitmap的chunks数组进行管理。其每一个元素代表着一个页大小的内存
根据前面的内存数据图和内存布局图可知，实际上这个系统中应该包含两块数组(buddys和slabs)用来管理内存。则chunks中的每一个元素包含两部分信息——当前页所属的内存对象是buddy还是slab；当前页所述的内存对象是否在在使用(slabs数组该字段恒为在使用中)；当前页所述的内存对象在对应数组中的下标。

其结构如下所示
chunks数组元素结构

chunks数组初始化

实际上，我们需要管理所有可用于分配的内存对象。将这些对象以页为单位，分别对应到chunks数组的每一个元素即可。

1
2
3
4
5
6
7
8
9
10
/*
 * 首先需要预留一部分的内存，用来存储管理heap的结构
 * 其次，剩余部分的内存，其起始地址部分应该MAXSIZE大小对齐
 * 
 * 对于chunks结构来说，其管理所有的可用内存，并且按照1个uintptr_t对应一个页进行管理，
 * 其元素个数不超过     (heap.end - heap.start + PAGESIZE - 1) / PAGESIZE
 */
chunks = (uintptr_t*)heap.start;
chunks_size = (((uintptr_t)heap.end) - ((uintptr_t)heap.start) + PAGESIZE - 1) / PAGESIZE;
printf("chunks: [%X, %X), chunks_size: %D\n", (uint64_t)(uintptr_t)chunks, (uint64_t)(uintptr_t)(chunks + chunks_size), (uint64_t)chunks_size);

chunks的API

根据前面的分析，chunks数组就是用来获取当前chunk的诸如大小等信息的。
这里提供了一系列宏。其只需要传入chunk地址，即可获取该内存对象的所有信息

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/*
 * 前面已经描述了chunks每个元素的结构，这里给出操作该结构的宏
 */
//也就是uintptr_t中，标志位的起始bit位
#define CHUNKS_FLAG_SIZE                (1)
#define CHUNKS_FLAG_BUDDY               (0)
#define CHUNKS_FLAG_SLAB                (1)

#define CHUNKS_STATUS_SIZE              (1)
#define CHUNKS_STATUS_INUSE             (0)
#define CHUNKS_STATUS_UNUSE             (1)

#define CHUNKS_IDX_SIZE                 (sizeof(uintptr_t) * 8 - CHUNKS_STATUS_SIZE - CHUNKS_FLAG_SIZE)

#define CHUNKS_IDX_MASK                 ((((uintptr_t)1) << (CHUNKS_IDX_SIZE)) - 1)
#define CHUNKS_STATUS_MASK              ((((uintptr_t)1) << (CHUNKS_IDX_SIZE + CHUNKS_STATUS_SIZE)) - 1 - CHUNKS_IDX_MASK)
#define CHUNKS_FLAG_MASK                ((~((uintptr_t)0)) - CHUNKS_IDX_MASK - CHUNKS_STATUS_MASK)


#define CHUNKS_VAL_GET_IDX(val)         (((uintptr_t)(val)) & CHUNKS_IDX_MASK)
#define CHUNKS_VAL_GET_STATUS(val)      ((((uintptr_t)(val)) & CHUNKS_STATUS_MASK) >> (CHUNKS_IDX_SIZE))
#define CHUNKS_VAL_GET_FLAG(val)        ((((uintptr_t)(val)) & CHUNKS_FLAG_MASK) >> (CHUNKS_IDX_SIZE + CHUNKS_STATUS_SIZE))

#define CHUNKS_VAL_SET_IDX(ptr, val) \
    (*((uintptr_t*)(ptr))) &= (~CHUNKS_IDX_MASK); \
    (*((uintptr_t*)(ptr))) |= (((uintptr_t)(val)) & CHUNKS_IDX_MASK)
#define CHUNKS_VAL_SET_STATUS(ptr, val) \
    (*((uintptr_t*)(ptr))) &= (~CHUNKS_STATUS_MASK); \
    (*((uintptr_t*)(ptr))) |= ((((uintptr_t)(val)) << (CHUNKS_IDX_SIZE)) & CHUNKS_STATUS_MASK)
#define CHUNKS_VAL_SET_FLAG(ptr, val) \
    (*((uintptr_t*)(ptr))) &= (~CHUNKS_FLAG_MASK); \
    (*((uintptr_t*)(ptr))) |= ((((uintptr_t)(val)) << (CHUNKS_IDX_SIZE + CHUNKS_STATUS_SIZE)) & CHUNKS_FLAG_MASK)

#define CHUNKS_GET_IDX(addr)                (CHUNKS_VAL_GET_IDX(chunks[(((uintptr_t)(addr)) - chunks_base) / PAGESIZE]))
#define CHUNKS_GET_STATUS(addr)             (CHUNKS_VAL_GET_STATUS(chunks[(((uintptr_t)(addr)) - chunks_base) / PAGESIZE]))
#define CHUNKS_GET_FLAG(addr)               (CHUNKS_VAL_GET_FLAG(chunks[(((uintptr_t)(addr)) - chunks_base) / PAGESIZE]))
#define CHUNKS_SET_IDX(addr, idx)           CHUNKS_VAL_SET_IDX(chunks + ((((uintptr_t)(addr)) - chunks_base) / PAGESIZE), (idx))
#define CHUNKS_SET_STATUS(addr, status)     CHUNKS_VAL_SET_STATUS(chunks + ((((uintptr_t)(addr)) - chunks_base) / PAGESIZE), (status))
#define CHUNKS_SET_FLAG(addr, flag)         CHUNKS_VAL_SET_FLAG(chunks + ((((uintptr_t)(addr)) - chunks_base) / PAGESIZE), (flag))

伙伴算法

伙伴算法，或者Buddy算法，是一种能有效提高内存利用率，且降低内部碎片的内存管理算法。

初始化伙伴算法

由于伙伴算法涉及到对象的拆分和合并，其往往需要互斥的访问一些共享资源(比如位图等)。因此在本实验中，其属于实验指南中的”slow path”，用来分配大内存或者当用于分配中、小内存的slab机制耗尽资源时的内存分配
由于伙伴算法中所有的内存对象都是连续分布的，且其大小都是$2^{i}$;因此只要内存地址最小的内存对象，其内存地址是对齐的，则后面所有的内存地址都是自动对齐的。
分配的时候，由于内存对象位于双向链表的表头数组中，其每一个元素都是大小相同的内存对象组成的双向循环链表，则我们根据内存对象在表头数组中的下标，可以直观的知道该内存对象对应的大小信息;但是在释放的时候，由于内存对象中并没有存储内存的大小信息，但是前面的chunks数组中保存内存对象的大小，从而在释放内存对象时，仅仅根据其虚拟地址获取内存对象的大小信息
最后，这里为了避免初始化时间过长，则默认一开始所有的内存对象的大小都是允许分配的最大的内存大小(实验指导中规定的是16MB)——这样前面映射数组初始化为对应的下标即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/*
 * 初始化buddys数组
 * 一方面，需要初始化buddys数组中的锁结构，以及其fd、bk值
 * 
 * 另一方面，要将剩余的所有内存，都切分成MAXSIZE的CHUNK，插入到相关的buddys最后一个数组元素的链表中
 */
static void
buddys_init(uint64_t start, uint64_t end)
{
  //其start和end必须是MAXSIZE对齐的，从而可以将内存全部分割成MAXSIZE大小的
  panic_on(start % MAXSIZE, "error start");
  panic_on(end % MAXSIZE, "error end");

  chunks_base = start;

  //首先初始化buddys数组中的索结构，以及fd、bk值
  for(int i = 0; i < buddys_size; ++i) {
    buddys[i].fd = buddys[i].bk = &buddys[i];
    lock_init(&(buddys[i].un.lock));
  }


  /*
   * 依次插入剩余的内存即可
   *
   * 首先设置chunks字段相关信息
   * 然后将其插入到链表中即可
   */
  for(uintptr_t iter = start; iter < end; iter += MAXSIZE) {
    CHUNKS_SET_IDX(iter, buddys_size - 1);
    CHUNKS_SET_STATUS(iter, CHUNKS_STATUS_UNUSE);
    CHUNKS_SET_FLAG(iter, CHUNKS_FLAG_BUDDY);
    
    lock_acquire(&(buddys[buddys_size - 1].un.lock));
    list_insert((Chunk*)iter);
    lock_release(&(buddys[buddys_size - 1].un.lock));
  }

  printf("buddys_init(%X, %X), MAXSIZE:%X\n", start, end, (uint64_t)MAXSIZE);
}

获取内存

对于Buddy来说，要从Buddy中获取内存:
首先要检查申请大小——其申请的大小至少是PAGE_SIZE(4096B)，且最大不超过MAX_SIZE(16MB)，并且应该是$2^{i}$对齐的。
其次，获取锁结构，从而互斥的访问——这里需要自旋锁
然后，其从对应的表头数组下标处获取一个内存对象并返回即可;如果当前表头数组下标处没有可用的内存对象，则二分表头数组中最近的更大的内存对象，然后返回即可;如果仍然没有符合条件的，则返回NULL即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
/*
 * 将chunk插入到链表中
 * 此时的chunk已经完成所有的合并等工作，只需要进行插入即可
 * 
 * 其需要插入的数组，根据chunks的flag确定即可
 * 其需要插入的数组的下标，根据chunks的idx确定即可
 * 插入的时候，由于需要访问共享数据，需要确认上锁
 */
static void
list_insert(Chunk *chunk)
{
  //设置chunk的fence值，避免被覆盖
  chunk->un.fence = FENCE;

  Chunk *head = NULL;
  
  switch(CHUNKS_GET_FLAG(chunk)) {
    case CHUNKS_FLAG_BUDDY:
      panic_on(CHUNKS_GET_IDX(chunk) >= buddys_size, "error idx");
      head = &(buddys[CHUNKS_GET_IDX(chunk)]);
      break;

    case CHUNKS_FLAG_SLAB:
      panic_on(CHUNKS_GET_IDX(chunk) >= slabs_size, "error idx");
      head = &slabs[chunk->slabs_cpu_belongs_to][CHUNKS_GET_IDX(chunk)];
      break;

    default:
      panic("error flag");
  }

  //需要确认确实已经获取锁了
  panic_on(lock_try_acquire(&(head->un.lock)) != PMMLOCKED, "don't have the lock");

  CHUNK_CHECK_LIST(head);
  Chunk *bck = head, *fwd = bck->fd;

  /*
   * 将chunk插入到head和head->fd之间
   */
  chunk->bk = bck;
  chunk->fd = fwd;
  bck->fd = chunk;
  fwd->bk = chunk;

  CHUNK_CHECK_FENCE(chunk);
  CHUNK_CHECK_LIST(chunk);
}




/*
 * 将chunk从其链表上卸下来
 * 
 * 将链表卸下来的时候，在slabs中，其应该已经获取锁
 * 在buddys中，对于合并的卸载亦或是单纯卸载这一个节点，其锁应该都获取
 * 
 * 因此，在卸载的时候，其应该已经获取对应数组中的锁了
 * 另一方面，在卸载的时候；如果是buddys数组，应该将其对应的chunks中的元素idx置为CHUNK_IDX_MASK，从而在出错的时候，更容易检查出来
 */
static void
list_remove(Chunk *chunk)
{
  Chunk *head = NULL;
  switch(CHUNKS_GET_FLAG(chunk)) {

    case CHUNKS_FLAG_BUDDY:
      panic_on(CHUNKS_GET_IDX(chunk) >= buddys_size, "error idx");
      head = &buddys[CHUNKS_GET_IDX(chunk)];

      break;

    case CHUNKS_FLAG_SLAB:
      panic_on(CHUNKS_GET_IDX(chunk) >= slabs_size, "error idx");
      head = &slabs[chunk->slabs_cpu_belongs_to][CHUNKS_GET_IDX(chunk)];

      break;

    default:
      panic("error flag");
  }

  //需要确认确实已经获取锁了
  panic_on(lock_try_acquire(&(head->un.lock)) != PMMLOCKED, "don't have the lock");

  //检查一下完整性
  CHUNK_CHECK_FENCE(chunk);
  CHUNK_CHECK_LIST(chunk);

  Chunk *fwd = chunk->fd, *bck = chunk->bk;
  fwd->bk = bck;
  bck->fd = fwd;
}



/*
 * 即从buddy中分配内存
 *
 * 其size应该是已经对齐过，并且小于MAXSIZE的
 * 
 * 分配的时候，就是首先从低向高查询，找到第一个足够分配的内存
 * 如果该内存大小恰好对应申请的size大小，即可返回
 * 如果大于的话，则不停的二分拆分即可，将拆分的高地址一部分保留在buddy中即可
 */
static Chunk *
buddys_alloc(size_t size)
{
  int idx = BUDDY_CHUNK_SIZE2IDX(size);
  uintptr_t res = 0;

  panic_on(size < PAGESIZE, "size is too small");
  panic_on(size > MAXSIZE, "size is too big");
  panic_on(BUDDY_IDX2CHUNK_SIZE(idx) != size, "size is invalid");

  /*
   * 此时从低向高遍历
   * 找到第一个满足的chunk进行分配
   */
  int iter = idx;
  while(iter < buddys_size) {

    Chunk *head = &(buddys[iter]);
    lock_acquire(&(head->un.lock));

    if(head->fd != head) {
      res = (uintptr_t)head->fd;

      panic_on(CHUNKS_GET_IDX(res) != iter, "error idx");
      panic_on(CHUNKS_GET_STATUS(res) != CHUNKS_STATUS_UNUSE, "error status");
      panic_on(CHUNKS_GET_FLAG(res) != CHUNKS_FLAG_BUDDY, "error flag");

      CHUNKS_SET_STATUS(res, CHUNKS_STATUS_INUSE);
      list_remove((Chunk*)res);

      lock_release(&(head->un.lock));
      break;
    }

    lock_release(&(head->un.lock));
    ++iter;
  }

  //此时说明内存不足
  if(res == 0) { return NULL; }

  /*
   * 开始从高到低的二分的切割chunk
   * 然后设置chunks相关的idx，并且将其放回链表中
   */
  while(iter-- > idx) {

    Chunk *chunk = (Chunk*)(uintptr_t)(res + BUDDY_IDX2CHUNK_SIZE(iter)), *head = &(buddys[iter]);
    /*
     * 初始化时，所有的chunks的idx被设置为CHUNKS_IDX_MASK
     *                       status被设置为CHUNKS_FLAG_UNUSE
      *                      FLAG被设置为CHUNKS_FLAG_SLAB
     * 因此需要更改
     */
    CHUNKS_SET_FLAG(chunk, CHUNKS_FLAG_BUDDY);
    CHUNKS_SET_STATUS(chunk, CHUNKS_STATUS_UNUSE);
    CHUNKS_SET_IDX(chunk, iter);

    lock_acquire(&(head->un.lock));
    list_insert(chunk);
    lock_release(&(head->un.lock));
  }

  CHUNKS_SET_IDX(res, idx);
  CHUNKS_SET_STATUS(res, CHUNKS_STATUS_INUSE);

  debug_pmm("buddys_alloc(%X) res:%X", (uint64_t)size, (uint64_t)res);

  return (Chunk*)res;
}

释放内存

我们可以根据chunks获取当前待释放的内存对象的下标，因此我们可以将该chunk插入Buddy的表头数组的对应下标处的双向循环链表中即可
但是需要注意的是，在Buddy算法中，释放内存对象时需要进行合并——如果相邻的内存对象大小相同，其是已经被释放的内存对象，并且也是从同一个更大的内存对象中拆分的:则将临接内存对象从双向循环链表中摘下来，合并成原始的大内存对象，然后继续按照上面的步骤释放该合并过的内存对象即可
这里由于其拆分时是二分进行拆分的，因此寻找另一个被拆分的块可以通过异或快速进行定位，即Chunk *another_chunk = (Chunk*)(((uintptr_t)chunk) ^ size);
则根据上面的说明，Buddy算法的释放就是不断进行合并，直到内存对象没有可以合并的符合条件的相邻内存对象为止
需要小心的就是数据竞争。有可能之类刚刚判断完当前大小的相邻的chunk正在使用，后脚其相邻的chunk就被释放入内存，从而导致没有正常合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/*
 * 将内存释放到buddy中
 *
 * 注意一下，如果其是buddy_free，则其FLAG必然是CHUNKS_FLAG_BUDDY。
 * 而如果一个内存，其对应的CHUNKS_FLAG_SLAB，则其永远不可能成为BUDDY中的内存
 * 
 * 在任何时候，chunks始终保存着其对应的大小信息，无论是在buddys中，亦或是在slabs中，还是已经分配出去的chunk
 *
 * 需要注意的是,buddys数组在释放的时候，如果条件合适的话，要进行合并
 * 1. 如果释放的是chunk1，则要释放的内存地址是chunk2 = chunk1 ^ size
 * 2. chunk1的FLAG和chunk2的FLAG都为CHUNKS_FLAG_BUDDY
 * 3. chunk1和chunk2的IDX相同
 * 4. chunk1和chunk2的STATUS都为CHUNKS_STATUS_UNUSE
 */
static void
buddys_free(Chunk *chunk)
{
  panic_on(CHUNKS_GET_IDX(chunk) >= chunks_size, "error idx");
  panic_on(CHUNKS_GET_STATUS(chunk) != CHUNKS_STATUS_INUSE, "error status");
  panic_on(CHUNKS_GET_FLAG(chunk) != CHUNKS_FLAG_BUDDY, "error flag");

  int idx = CHUNKS_GET_IDX(chunk);
  Chunk *head = &(buddys[idx]);


  /*
   *
   * 这里需要注意的是，这里可能产生数据竞争
   * 因此，需要先获取当前下标对应的锁，避免两个chunk同时释放，或者一个刚刚判断完后，另一个chunk被申请走
   *
   */
  lock_acquire(&(head->un.lock));


  /*
   * 尝试合并相邻的buddys
   */
  while(idx < buddys_size - 1) {
    uintptr_t size = BUDDY_IDX2CHUNK_SIZE(idx);
    Chunk *another_chunk = (Chunk*)(((uintptr_t)chunk) ^ size);

    /*
     * 如果不满足以下条件
     * 则说明另一个chunk不能进行合并
     * 
     */
    if((CHUNKS_GET_IDX(another_chunk) != idx) || (CHUNKS_GET_STATUS(another_chunk) != CHUNKS_STATUS_UNUSE) || (CHUNKS_GET_FLAG(another_chunk) != CHUNKS_FLAG_BUDDY)) { break;}

    CHUNKS_SET_STATUS(another_chunk, CHUNKS_STATUS_INUSE);
    list_remove(another_chunk);
    lock_release(&(head->un.lock));


    chunk = chunk < another_chunk ? chunk : another_chunk;
    idx += 1;
    
    
    head = &(buddys[idx]);
    lock_acquire(&(head->un.lock));
  }


  CHUNKS_SET_IDX(chunk, idx);
  CHUNKS_SET_STATUS(chunk, CHUNKS_STATUS_UNUSE);

  debug_pmm("buddys_free(%X) size:%X", (uint64_t)(uintptr_t)chunk, (uint64_t)(BUDDY_IDX2CHUNK_SIZE(CHUNKS_GET_IDX(chunk))));

  list_insert(chunk);
  lock_release(&(head->un.lock));
}

slab机制

如果我们需要分配小于PAGE_SIZE大小的内存时，我们则使用slab机制。
其基本思想是通过Buddy算法申请一个页，然后将该页分割成对应大小(对齐后的请求大小)的chunk，然后进行分配和释放。
分配时，如果上次分配有剩余，则直接使用该剩余进行分配即可;否则，首先通过buddys_malloc申请一个页，然后将该页分割成数个对齐过的请求大小的块。将一个块作为返回的内存对象，其余内存对象插入到双向链表，在每个CPU的单独结构中进行管理即可
释放时，由于一个页被切割成相同大小的块，因此该块的信息和该内存地址对应的内存页在chunks元素的信息是完全相同的，从而可以知道该chunk的大小。在释放的时候，会根据其chunk大小，存放在每个CPU的slabs中。这里需要特别说明以下，为了提高效率，对于slab机制的页，在释放后不会进行合并——因为同一个页中的不同块可能是不同CPU进行释放的，如果进行合并，还可能涉及到数据竞争问题

初始化slab机制

正如前面所分析的，为了避免频繁的互斥，这里可以在每个CPU本地上提前准备一些频繁使用的相关大小的内存对象。在其申请的时候，则直接从这些内存对象中获取即可;释放的时候，则首先释放到该结构中。这样子，最大可能的避免了内存管理时的互斥操作。
如果当前CPU中相关结构里没有符合条件的内存对象，则可以在周边的CPU结构中进行遍历即可——这里为了避免自旋锁导致耗时过多，就简单的上锁即可;如果失败了不进行重试。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
 * 初始化slabs数组
 *
 * 不同于buddys数组的初始化，其只需要需要初始化每一个cpu的slabs数组中的锁结构，以及其fd、bk值
 */
static void
slabs_init(void)
{
  for(int cpu = 0; cpu < cpu_count(); ++cpu) {
    for(int idx = 0; idx < slabs_size; ++idx) {
      lock_init(&(slabs[cpu][idx].un.lock));
      slabs[cpu][idx].fd = slabs[cpu][idx].bk = &(slabs[cpu][idx]);
      

      printf("slabs[%D][%D]: %X; slabs[%D][%D].fd: %X; slabs[%D][%D].bk: %X\n", (uint64_t)cpu, (uint64_t)idx, (uint64_t)(uintptr_t)&(slabs[cpu][idx]),
        (uint64_t)cpu, (uint64_t)idx, (uint64_t)(uintptr_t)(slabs[cpu][idx].fd),
        (uint64_t)cpu, (uint64_t)idx, (uint64_t)(uintptr_t)(slabs[cpu][idx].bk)
      );
    }
  }

  printf("slabs_init\n");
}

获取内存

对于slab机制申请的内存大小，其不能超过PAGE_SIZE，否则直接使用Buddy算法进行分配即可。
首先，根据申请的大小，可以直接获取其slabs次序信息。然后，从本地CPU开始，遍历所有的CPU相关数据结构——如果其相关的slabs中包含有空闲的内存对象，则直接返回即可;否则继续遍历。这里需要注意的是，为了提高效率，这里的互斥并不是自旋锁实现的，即在上锁失败后不要进行重试。
如果遍历完所有CPU相关数据仍然未成功分配内存，则使用Buddy算法申请一个页，并将其拆分成数个大小等于申请大小的chunk，取出一个进行分配，剩下的插入到对应的slabs中即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
/*
 * 即从slabs中分配内存
 *
 * 其size应该是已经对齐过，并且大于等于MINSIZE, 小于PAGESIZE的
 * 
 * 分配的时候，从当前处理器开始，遍历的询问每一个处理器当前下标的slabs数组，如果存在则将其卸载，作为申请的内存即可
 * 如果都不存在的话，则向buddys申请一个PAGESIZE的内存，然后将其切分即可
 */
static Chunk *
slabs_alloc(size_t size)
{
  int idx = SLAB_CHUNK_SIZE2IDX(size);
  uintptr_t res = 0;

  panic_on(size < MINSIZE, "size is too small");
  panic_on(size >= PAGESIZE, "size is too big");
  panic_on(SLAB_IDX2CHUNK_SIZE(idx) != size, "size is invalid");

  int cpu = cpu_current();
  Chunk *head = &(slabs[cpu][idx]);
  do{

    /*
     * 如果是当前对应的cpu，则获取锁，然后进行遍历即可
     * 
     * 如果不是当前对应的cpu，需要注意的是，默认的情况是CPU主要从自己的slabs数组中获取，因此这里遍历的时候，不能阻塞获取锁，就尝试获取锁，
     * 如果获取成功就继续，否则遍历下一个即可
     */
    if(cpu == cpu_current()) { lock_acquire(&(head->un.lock)); }
    else {
      if(lock_try_acquire(&(head->un.lock)) == PMMLOCKED) { goto PREPARE_BEFORE_NEXT;}
    }

    if(head->fd != head) {
      res = (uintptr_t)head->fd;

      panic_on(CHUNKS_GET_IDX(res) != idx, "error idx");
      panic_on(CHUNKS_GET_STATUS(res) != CHUNKS_STATUS_INUSE, "error status");
      panic_on(CHUNKS_GET_FLAG(res) != CHUNKS_FLAG_SLAB, "error flag");

      list_remove((Chunk*)res);
      lock_release(&(head->un.lock));
      return (Chunk*)res;
    }
    lock_release(&(head->un.lock));

    PREPARE_BEFORE_NEXT:
      cpu = (cpu + 1) % cpu_count();
      head = &(slabs[cpu][idx]);

  }while(cpu != cpu_current());


  //如果执行到此处，说明所有的cpu的slabs目前都没有可用的chunk，则直接从buddy中申请一块即可。切分的剩余的chunk，全部插入到当前cpu的slabs中即可
  panic_on(res != 0, "error res");
  if((res = (uintptr_t)buddys_alloc(PAGESIZE)) == 0) { return NULL; }
  panic_on(BUDDY_IDX2CHUNK_SIZE(CHUNKS_GET_IDX(res)) != PAGESIZE, "error idx");
  panic_on(CHUNKS_GET_STATUS(res) != CHUNKS_STATUS_INUSE, "error status");
  panic_on(CHUNKS_GET_FLAG(res) != CHUNKS_FLAG_BUDDY, "error flag");


  /*
   * 更改chunks属性
   * 由于slabs不会进行合并，此处是永久性的改变
   * 
   * 首先是flag，将其更改为CHUNKS_FLAG_SLAB
   * 对于idx，更改为idx即可
   */
  CHUNKS_SET_FLAG(res, CHUNKS_FLAG_SLAB);
  CHUNKS_SET_IDX(res, idx);


  /*
   * 下面切割内存，并依次插入到slabs中即可
   *
   * 注意，还需要将slabs_cpu_belongs_to字段设置为当前cpu
   */
  uintptr_t gap = SLAB_IDX2CHUNK_SIZE(idx);
  for(uintptr_t iter = gap; iter < PAGESIZE; iter += gap) {
    Chunk *chunk = (Chunk*)(iter + res);
    chunk->slabs_cpu_belongs_to = cpu;
    lock_acquire(&(head->un.lock));
    list_insert(chunk);
    lock_release(&(head->un.lock));
  }

  debug_pmm("slabs_alloc(%X) res:%X", (uint64_t)size, (uint64_t)res);

  return (Chunk*)res;
}

释放内存

对于slab机制中的释放，由于其不会将slab中所有的chunk重新进行合并，因此其释放非常简单——直接插入到当前CPU的Slab_Per_Cpu中的链表中即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
 * 将内存释放到slabs中
 *
 * 注意一下，如果其是slabs_free，则其FLAG必然是CHUNKS_FLAG_SLABS。
 * 
 * 在任何时候，chunks始终保存着其对应的大小信息，无论是在buddys中，亦或是在slabs中，还是已经分配出去的chunk
 * 
 * 与buddys不同的是，其需要设置slabs_cpu_belongs_to字段
 */
static void
slabs_free(Chunk *chunk)
{
  panic_on(CHUNKS_GET_IDX(chunk) >= slabs_size, "error idx");
  panic_on(CHUNKS_GET_STATUS(chunk) != CHUNKS_STATUS_INUSE, "error status");
  panic_on(CHUNKS_GET_FLAG(chunk) != CHUNKS_FLAG_SLAB, "error flag");

  debug_pmm("slabs_free(%X) size:%X", (uint64_t)(uintptr_t)chunk, (uint64_t)(SLAB_IDX2CHUNK_SIZE(CHUNKS_GET_IDX(chunk))));

  chunk->slabs_cpu_belongs_to = cpu_current();
  Chunk *head = &(slabs[cpu_current()][CHUNKS_GET_IDX(chunk)]);
  lock_acquire(&(head->un.lock));
  list_insert(chunk);
  lock_release(&(head->un.lock));
}

kalloc和kfree

实际上，这两个只不过是分别对于buddys_malloc和slabs_malloc、buddys_free和slabs_free的包装而已。
对于kalloc来说，其根据申请的内存大小的不同，分别调用buddys_malloc或slabs_malloc——如果对齐后的内存大小小于PAGE_SIZE，则调用slabs_malloc即可;否则，直接调用buddys_malloc进行申请
对于kfree来说，其根据chunks提供的宏进行判断——如果是slabs对应的的内存对象，则通过slabs_free进行释放即可;否则，需要通过buddys_free进行释放

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
static void *
kalloc(size_t size)
{
  if(size > MAXSIZE) { return NULL; }
  if(size < MINSIZE) { size = MINSIZE; }

  size_t size_align = request_size2mem_size(size);

  panic_on(size_align < MINSIZE, "size is too small");
  panic_on(size_align > MAXSIZE, "size is too big");

  void *res = size_align < PAGESIZE ? slabs_alloc(size_align) : buddys_alloc(size_align);

  debug_pmm("kalloc(%X) = %X", (uint64_t)size, (uint64_t)(uintptr_t)res);

  return res;
}


static void
kfree(void *ptr)
{
  if(ptr == NULL) {return;}
  panic_on((uintptr_t)ptr > (uintptr_t)heap.end, "invalid ptr");
  panic_on((uintptr_t)ptr < (uintptr_t)chunks_base, "invalid ptr");

  switch (CHUNKS_GET_FLAG(ptr))
  {
  case CHUNKS_FLAG_BUDDY:
    buddys_free(ptr);
    break;
  
  case CHUNKS_FLAG_SLAB:
    slabs_free(ptr);
    break;

  default:
    panic("error flag");
  }

  debug_pmm("kfree(%X)", (uint64_t)(uintptr_t)ptr);
}

实验结果

执行make test=pmm smp=8 run命令，调用测试框架中的压力测试，结果如下图所示
实验结果