原文：https://cs162.org/static/hw/hw-memory/
归档参考（Wayback）：https://web.archive.org/web/20251215163710/https://cs162.org/static/
你在 Project 1 中实现的 Pintos userspace 有一个重大限制——user program 中无法进行任何 dynamic memory allocation。目前，user process 中的所有 memory 要么是从 executable 加载的（例如 code、globals），要么是在 stack 上分配的。
在本 homework 中，你将提供一种方式，让 user process 能显式地向 Pintos kernel 请求更多 memory，并利用这一特性自行实现 malloc、realloc 和 free。
登录你的 VM，并从 staff repository pull skeleton code：
cd ~/code/personal
git pull staff main
cd hw-memory
若你在本地完成过任何先前的 assignments，请务必也运行 git pull personal main。
来源：https://cs162.org/static/hw/hw-memory/docs/sbrk/
来源：https://cs162.org/static/hw/hw-memory/docs/sbrk/introduction/
- Compilation
- Skeleton
在本部分 homework 中，你需要为 Pintos 扩展 sbrk system call，以便你的 dynamic memory allocator 能向 operating system 请求 memory。
要为本部分构建代码并运行 tests：
cd ~/code/personal/hw-memory/pintos/src/memory
make check
本部分代码位于 hw-memory 目录下的 pintos/src 子目录中。
本 homework 建立在你在 Project 1 中实现的 Pintos userspace 之上（以及下文提到的其他一些已实现功能）。但与 Project 1 不同，这是一份 individual assignment。你 不应 与 group members 共享代码来完成本 assignment！为简化后勤安排，我们提供了完成本 assignment 所需的、来自 Project 1 的最低限度功能实现。该实现基于较旧版本的 Pintos，且并非对 Project 1 功能的完整实现——因此，你应基于我们在 starter code 中提供的 userspace 实现来完成本 assignment，而不是 使用你们 group 在 Project 1 中的实现。话虽如此，本 assignment 对 Project 1 的依赖性质是：虽然 Pintos userspace 的某些功能必须正常工作，本 assignment 才有意义（例如，你必须能够启动一个 user process，它才能向 kernel 请求 heap memory），但你为本 assignment 编写的代码并不直接依赖 Project 1 功能的具体实现。
Starter code 实现了以下内容。
- 完成 Project Pregame 所需的 one-line do-nothing hack。
- 针对 file descriptor 1（stdout）的 write system call。
- 每个 process 打开、read、write 以及 close 单个 file 的能力。
- 使用 page fault handler 对所提供 system calls 进行 argument validation。
- Pintos 中 malloc/calloc/realloc/free 的实现。
值得注意的是，所提供的 starter code 不 提供在 command line 上传入 arguments、exec 新 process，或打开多个 files 的能力。我们选择只实现上述条目，以尽量减少你需要阅读的代码量，并简化部分实现（下文讨论）。
以下是你在本 assignment 中可能用到的一些文件。
threads/palloc.c
Page allocator。
threads/vaddr.h
在 Pintos 中处理 virtual addresses 的 helper functions。
userprog/process.c
加载 ELF binaries、启动 processes，并在 context switch 时切换 page tables。基于你在 Project User Programs 中的经验，你应对此代码较为熟悉。
userprog/pagedir.c
管理 page tables。你很可能不需要修改此代码，但可能需要调用其中的一些 functions。
userprog/syscall.c
这是一个基本的 system call handler，实现了上述 system calls。
lib/user/syscall.c
为 user programs 提供从 C program 调用 system calls 的 library functions。每个 function 使用 inline assembly code 来准备 syscall arguments 并调用 system call。我们期望你理解 syscalls 所使用的 calling conventions。
lib/user/stdlib.S
为链接进 Pintos user applications 的 C standard library 提供 library functions，即实现 malloc、calloc、realloc 和 free。
lib/syscall-nr.h
此文件定义了每个 syscall 的 syscall numbers。
你应仔细阅读 thread/vaddr.h 与 userprog/pagedir.h 中的 functions，因为其中许多在本 assignment 中会对你有用。
来源：https://cs162.org/static/hw/hw-memory/docs/sbrk/pages/
- Allocating pages
- Mapping a page into a virtual address space
- Summary and example
使用 threads/palloc.h 中的下列 functions 在 Pintos kernel 中分配与释放 pages。
void* palloc_get_page(enum palloc_flags);
void* palloc_get_multiple(enum palloc_flags, size_t page_cnt);
void palloc_free_page(void* page);
void palloc_free_multiple(void* pages, size_t page_cnt);
palloc functions 使用 bitmap 来跟踪哪些 pages 空闲、哪些 pages 已分配。flags 参数是下列选项的 bitmask。
enum palloc_flags {
PAL_ASSERT = 001, /* Panic on failure. */
PAL_ZERO = 002, /* Zero page contents. */
PAL_USER = 004 /* User page. */
};
Pages 的集合被划分为两个独立的 pools：user pool 与 kernel pool。Kernel pool 中的 pages 供 kernel 内部使用（例如 kernel threads 的 stack），user pool 中的 pages 则用于映射到 user processes 的 virtual address spaces。这种分离的原因是：防止在 user programs 耗尽 memory 时导致 kernel 失败。PAL_USER flag 告诉 palloc function 从 user pool 分配所请求的 pages。否则，它将从 kernel pool 分配所请求的 pages。若你打算将某个 page 映射到某个 process 的 virtual address space，你应从 user pool 使用 PAL_USER 来分配它。
struct thread 的 pagedir member 是指向该 process 的 page table 的 pointer。在切换到某个 process 时，Pintos 使用 pagedir_activate function，通过设置 page directory base register（%cr3），开始使用该 process 的 page table 进行 address translation。注意，整个 kernel memory 都被映射到每个 process 的 virtual address space 中、位于 PHYS_BASE 及以上的 addresses，因此只要你访问的是 kernel memory，所有 process 的 page tables 都是可互换的。因此，我们有时将 PHYS_BASE 及以上的 addresses 称为 kernel virtual addresses。
与某个 kernel virtual address 对应的 physical address，可通过从中减去 PHYS_BASE 来计算。原则上这一点不必成立，但 Pintos 将其 page tables 设置成了这样。vtop 与 ptov（在 threads/vaddr.h 中）是为你执行此转换的 helper functions，但我们不期望你在本 assignment 中必须使用这些 functions。
给定一个在 kernel virtual memory 中分配的 page，可通过调用 pagedir_set_page 将其映射到某个 process 的 virtual address space；该函数会处理两级层次化 page table 的遍历，并按需分配 leaves。传给 pagedir_set_page 的两个 arguments 分别是：该 page 应映射到的 user process 中的 virtual address，以及要映射的 page 的 kernel virtual address。pagedir_set_page 会查找 physical page number 并为你创建必要的 page table entries，因此你应传入 kernel virtual address，而不是 physical page number。 一旦你将该 page 映射到 process 的 virtual address space，你不必担心释放它；当 process 退出时，process_exit function 会调用 pagedir_destroy，后者会对映射到该 process address space 的所有 pages 调用 palloc_free_page。若你希望即使在 process 结束后该 page 仍保持已分配状态，应先使用 pagedir_clear_page 将其从 page table 中移除。
注意，你使用 palloc_get_page 分配的 pages 可能先前已被分配而后又被释放，因此可能包含上次分配时留下的数据。若它曾被映射到某个 user process，则可能包含先前 user program 的数据。为正确实施 protection，你应在将 page 映射到 user process 之前初始化其内容。通常的做法是将该 page 中的所有 bytes 设为零， 除非在特殊情况下该 page 应包含特定数据（例如向 process 加载新 code，或从 disk 换回某个 page）。在任何情况下，都不应该因为某个 physical page frame 被重用，而使 kernel 或其他 processes 使用的 memory 对某个 process 可见。
总结而言，将一个全新的 page 映射到某个 process 的 virtual address space 的做法如下。
- 使用 palloc_get_page 并传入 PAL_USER flag，从 user pool 分配该 page。
- 将该 page 的内容清零，可通过使用 memset，或在分配该 page 时传入 PAL_ZERO flag（例如 palloc_get_page(PAL_ZERO | PAL_USER)）。
- 使用 pagedir_set_page 将该 page 映射到某个 process 的 virtual address space。
- 当 process 退出且 pagedir_destroy 被调用时，该 page 会被释放。或者，若你希望在其他时间释放该 page，可用 pagedir_clear_page 将其从 page table 中移除，稍后再用 palloc_free_page 释放它。
一个简单示例见 process.c 中的 setup_stack 与 install_page functions。我们强烈建议你在尝试本 homework 之前，先复习这些 functions 并理解这个简单示例。
来源：https://cs162.org/static/hw/hw-memory/docs/sbrk/syscall-implementation/
- Process memory
- Requesting memory from the operating system
- Determining the start of the heap
- Manipulating the segment break
建议你先通读 process.c 中的 start_process 与 load functions。考虑你必须在这些位置进行哪些新的 initialization，才能支持前面各节所概述的 heap 功能。
每个 process 都有自己的 virtual address space。该 address space 的部分通过 address translation 映射到 physical memory。为了构建 memory allocator，我们需要理解 heap 本身是如何组织的。这里我们描述一个 process 的 memory layout，并重点说明 Linux process 中 heap 的结构。你需要在 Pintos 中用 sbrk system call 实现一个简化版的 heap。
Heap 是一块 memory 空间，在 process 的 virtual address space 中是连续的，并有三个边界：
- Heap 的底部。
- Heap 的顶部，称为 break。Break 可通过 brk 与 sbrk 改变。Break 标记 mapped memory space 的末尾。在 break 之上是尚未被 operating system 映射到 physical addresses 的 virtual addresses。为简单起见，本 assignment 你只需在 Pintos 中实现 sbrk。你不必处理 brk。你应将 sbrk 实现为 Pintos 中的一个新 system call。
- Heap 的 hard limit，break 不能超越该限制。更多信息见 Resource limits。为简单起见，本 assignment 你不应实现 heap size 的 hard limit。
在本 assignment 中，你将在 mapped region 中分配 memory blocks，并在需要扩展 mapped region 时适当地移动 break。
最初，heap 的 mapped region 大小为 0。要扩展 mapped region，我们必须操纵 break 的位置。做法是通过 sbrk，其定义在 lib/user/syscall.c 中：
void* sbrk(intptr_t increment);
你的任务是通过在 src/userprog/syscall.c 中实现 syscall_sbrk function 来实现 sbrk syscall：将 break 的位置增加 increment bytes，并返回先前 break 的 address（即若 increment 为正，则为新映射 memory 的起始处）。你需要对 src/lib/syscall-nr.h、src/lib/user/syscall.c，以及 src/userprog/syscall.c 中的 syscall handler 做相应修改。要获取 break 的当前位置，传入 increment 为 0。在 Linux 上运行 man 2 sbrk 可获得更多有用信息。
要实现 syscall_sbrk function，你需要为每个 process 跟踪两个变量：heap 的起始位置，以及 segment break（heap 的末尾）。这些应维护在 struct thread 中。我们在下文说明如何使用这些变量。
你应确保 process 的 heap 位于该 process 的 code 以及从 executable 加载的其他 data 之上（即处于更高的 virtual address）。你应在 program 被加载时确定 heap 应从哪个 address 开始，此后在整个 process 生命周期中应保持固定。请仔细查看 process.c 中的 load function。对于 executable 中的每个 loadable segment（还记得 Homework 0 中的 segments 吗？），load 会根据 executable 中指定的 read/write permissions 与 virtual address，在该 process 的 virtual address space 中分配 pages，并将 executable file 中的 data 读入这些 pages。根据 segments 被加载到 memory 中的位置，你应确定 heap 应从哪个 address 开始。
ELF executable format 保证 loadable segments 会按 virtual address space 升序列在 executable 中。因此，你应在 load function 处理的最后一个 loadable segment 之后的某个 virtual address 处启动 heap。 我们建议选择一个 page-aligned address 作为 heap 的起始。
要了解更多关于 ELF 的信息，请阅读 man 5 elf。
Segment break 应为 heap 末尾之后的第一个 address，因此你可以在加载 process 后将 data segment break 初始化为 heap 的起始。你应仅在响应 sbrk system calls 时移动它。User program 应能够从 heap 的起始处开始写入 data，一直写到（但不包括）segment break。 若 user program 移动 segment break 以增大 heap，你应按需分配 pages 并将它们映射到 user 的 virtual address space。若 user program 移动 segment break 以减小 heap，你应按需释放不再包含 heap 任何部分的 pages。仅当 segment break 跨越 page boundary 时，你才需要分配或释放 pages。
Memory 只能以 pages 为量子映射到 virtual address space。因此，若 segment break 不是 page-aligned，则 system break 之后、下一个 page boundary 之前的 memory 可被 process 访问，这是可接受的。更多信息见 Unmapped region and no man’s land。
为 process 的 heap 分配额外 pages 可能会失败，例如当 user memory pool 耗尽且 palloc_get_page 失败时。若 sbrk 失败，净效果应为：sbrk 返回 (void*) -1，且 segment break 与 process heap 不受影响。在这种情况下，你可能需要撤销到目前为止已做的任何操作。
最后，真实的 operating systems 可能会像 stack growth 那样惰性地为 sbrk 分配 pages。虽然 sbrk 会移动 segment break，但直到 user program 实际尝试访问其 heap 中的 data 时，pages 才会被分配。为简单起见，你不必实现这一优化。
来源：https://cs162.org/static/hw/hw-memory/docs/sbrk/additional-information/
- Unmapped region and no man’s land
- Resource limits
我们此前看到，break 标记 mapped virtual address space 的末尾。按此假设，访问 break 之上的 addresses 应触发错误（“bus error” 或 “segmentation fault”）。
Virtual address space 以 pages 为量子进行映射（通常是 4096 bytes 的某个倍数）。当调用 sbrk 时，operating system 必须为 heap 映射更多 memory。为此，它会将一整页 physical memory 映射到 heap 的 mapped region。此时，break 有可能并未正好落在 page boundary 上。在这种情况下，break 与 page boundary 之间的 memory 状态如何？事实证明，这段 memory 是可访问的，尽管它位于 break 之上，理论上应是 unmapped 的。与此问题相关的 bugs 尤其隐蔽，因为若你对该 “no man’s land” 进行读或写，不会发生任何错误。
在 Homework 0 中，你曾简要探索过 getrlimit syscall。在像 Linux 这样的现代 operating systems 中，processes 对其 resource usage 有限制。例如，stack 与 heap 的最大大小受资源 RLIMIT_STACK 与 RLIMIT_DATA 的限制约束（见 man 2 getrlimit）。这些资源中的每一项都有 hard limit 与 soft limit。Process 可以提高自己的 soft limits；soft limit 的存在是为了尽早捕获 bugs（例如 resource leaks）：若 process 使用的 resources 超出预期，就会导致错误。Hard limit 只能由 superuser（root）提高，其存在是为了防止 resource abuse。对本 assignment，不要对 stack size 或 heap size 设置 upper bound。你不需要实现 resource limits。
来源：https://cs162.org/static/hw/hw-memory/docs/library_functions/
来源：https://cs162.org/static/hw/hw-memory/docs/library-functions/introduction/
- Compilation
- Skeleton
- Background
- Heap data structure
在本部分 assignment 中，你将从零实现自己的 memory allocator。
要编译本部分的代码：
cd ~/code/personal/hw-memory/mm_alloc
make
本部分代码位于 hw-memory 目录下的 mm_alloc 子目录中。
你会在 mm_alloc.c 中找到一个简单的 skeleton。mm_alloc.h 定义了一个包含三个 functions 的接口：mm_malloc、mm_free、mm_realloc。你需要实现这些 functions。不要更改其中任何一个的 headers！
所给的 mm_test.c 会执行一些 sanity checks，但并非穷尽性测试。我们建议你在本地测试时，通过修改此文件编写一些自定义 tests。
malloc 与 sbrk 的 man pages 是本 assignment 的优秀参考资料。注意：你必须使用 sbrk 来分配 heap region。你不得调用标准的 malloc/free/realloc functions。
关于 process memory 如何工作，你可能需要回顾 homework 的第一部分。在本部分中，你将在 heap 的 mapped region 中分配 memory blocks，并使用 sbrk syscall 适当地移动 break。最初，heap 的 mapped region 大小为 0。
Heap 的一个简单 memory allocator 可以用 linked list 数据结构实现。Linked list 的元素将是 heap 上已分配的 memory blocks。为组织我们的数据，每个已分配的 memory block 前面都会有一个包含 metadata 的 header。
对每个 block，我们包含以下 metadata：
prev, next
指向描述相邻 blocks 的 metadata 的 pointers
free
描述该 block 是否空闲的 Boolean
size
该 memory block 的已分配大小
你也可以考虑使用 flexible array member 作为指向该 memory block 的 pointer。
来源：https://cs162.org/static/hw/hw-memory/docs/library-functions/memory-allocator/
- Allocation
- Deallocation
- Reallocation
构建 memory allocator 有许多方式。在本部分 homework 中，你将按上一节所述，使用 memory blocks 的 linked list 来实现 memory allocator。在本节中，我们将说明在该方案下 allocation、deallocation 与 reallocation 应如何工作。要使你的实现成功，你需要修改 mm_alloc.c。
void* mm_malloc(size_t size);
User 会传入所请求的 allocation size。确保返回的 pointer 指向已分配空间的起始处，而不是你的 metadata header。一种寻找可用 memory 的简单算法称为 first fit。当你的 memory allocator 被调用来分配一些 memory 时，它会遍历其 blocks，直到找到一块足够大的空闲 memory block。
以下是需要注意的一些实现细节。
- 若找不到足够大的空闲 block，使用
sbrk在 heap 上创建更多空间。 - 若你找到的第一块 memory 大到既能容纳新分配的 block，还能再容纳另一个 block，则将该大 block 一分为二：一块用于存放新分配的 block，另一块作为剩余的空闲 block。
- 若你找到的第一块 memory 只比你需要的稍大一些，但还不足以再放一个新 block（即不足以容纳一个新 block 的 metadata），要注意：在新分配的 block 末尾会有一些未使用的空间。
- 若无法分配所请求的新大小，返回
NULL。 - 若所请求的 size 为 0，返回
NULL。 - 出于评分目的，请在返回指向已分配 memory 的 pointer 之前，对你分配的 memory 做 zero-fill。
void mm_free(void* ptr);
当 user 使用完其 memory 时，会调用你的 memory allocator 来释放 memory，并传入他们从 mm_malloc 收到的 pointer ptr。注意，deallocation 并不意味着你必须把 memory 归还给 OS；你只需现在能够将该 block 用于将来的 allocation。
以下是需要注意的一些实现细节。
- 作为你在 allocation 过程中拆分 blocks 的副作用，你可能会遇到 fragmentation 问题：即使你有足够大的一段空闲 memory，你的 blocks 也可能变得太小，无法满足大型 allocation 请求。为解决此问题，在释放一个与其他空闲 block(s) 相邻的 block 时，你必须 coalesce 连续的空闲 blocks。
- 若传入
NULLpointer，你的 deallocation function 应什么都不做。
void* mm_realloc(void* ptr, size_t size);
Reallocation 应将位于 ptr 的已分配 block 调整为 size。一种建议的实现是：先 mm_malloc 一块指定大小的 block，将旧 data memcpy 到新 block，最后再调用 mm_free(ptr)。请确保处理以下 edge cases。
- 若无法分配所请求的新大小，返回
NULL。在这种情况下，不要修改原来的 block。 mm_realloc(ptr, 0)等价于调用mm_free(ptr)并返回NULL。mm_realloc(NULL, n)等价于调用mm_malloc(n)。mm_realloc(NULL, 0)等价于调用mm_malloc(0)，应直接返回NULL。- 请确保处理 size 小于原始 size 的情况。
来源：https://cs162.org/static/hw/hw-memory/docs/submission/
要提交并推送到 autograder，请把你的更改 push 到你的 repo，这应会触发 autograder。你应在几分钟内收到来自 autograder 的 email。若半小时内仍未收到来自 autograder 的 email，请通过 Ed 上的 private post 通知 staff。
你的代码不应包含多余的或 debugging 用的 print statements，因为这会干扰（原文：interefere）autograder。