：Eliminate allocation from sbrk() (easy))
Eliminate allocation from sbrk() (easy)实验目标这是 Lab5Lazy page allocation惰性页分配的第一步也是整套按需分页大戏的序章。本步只做一件事从sbrk()系统调用里删掉真正的内存分配只记一笔我分配了多大的账。练习目标改写sys_sbrk()去掉growproc()调用仅让进程sz地址空间上界增长不建立任何物理映射。理解lazy allocation惰性/按需分配的核心思想内存不在sbrk时一次性分配而是等到进程真正访问那块地址、触发缺页时才分配。亲手观察这一步会引发什么崩溃想清楚崩溃的完整链路——这正是下一步真正实现 lazy handler要修的靶子。官方 lab 原文对这一步的定位非常清楚Your first task is to delete page allocation from thesbrk(n)system call implementation…sbrk(n)grows the process’s memory size bynbytes, and then returns the start of the newly allocated region (i.e., the old size). Your newsbrk(n)should just increment the process’s size (myproc()-sz) bynand return the old size.It should not allocate memory— so you should delete the call togrowproc()(but you still need to increase the process’s size!).前置知识1.sbrk与进程堆内存xv6的用户程序通过sbrk()向内核申请堆内存。官方 lab 原文定义得很直白Xv6 applications ask the kernel for heap memory using thesbrk()system call…sbrk(n)grows the process’s memory size bynbytes, and then returns the start of the newly allocated region (i.e., the old size).在标准 xv6 里sys_sbrk的核心是growproc(n)→uvmalloc()后者干两件事用kalloc()从空闲链表抠出一块物理内存用mappages()在页表里把新虚拟地址映射到这块物理页。也就是说传统实现是申请即分配——sbrk一调用物理页马上就位。2. 为什么要 lazy官方 lab 原文的思想内核One of the many neat tricks an O/S can play with page table hardware is lazy allocation of user-space heap memory… It can take a long time for a kernel to allocate and map memory for a large request. Consider, for example, that a gigabyte consists of 262,144 4096-byte pages… In addition,some programs allocate more memory than they actually use(e.g., to implement sparse arrays), or allocate memory well in advance of use. To allowsbrk()to complete more quickly in these cases, sophisticated kernels allocate user memorylazily. That is,sbrk()doesn’t allocate physical memory, but justremembers which user addresses are allocated and marks those addresses as invalid in the user page table. When the process first tries to use any given page of lazily-allocated memory, the CPU generates apage fault, which the kernel handles by allocating physical memory, zeroing it, and mapping it.这段话是整套 Lab5 的题眼提炼成三句话大请求慢1GB 要建 26 万个页表项逐个分配很贵。超额/提前分配普遍稀疏数组、预分配缓冲区大部分内存根本用不上。lazy 的做法sbrk只记账改sz 把对应页表项标记为无效第一次真正访问时才由缺页中断触发分配。这叫demand paging按需分页。3. RISC-V 缺页异常与scause编码进程访问一块未被映射的虚拟地址时MMU 硬件发现页表项无效 → CPU 触发页错误异常page fault陷入内核usertrap()。RISC-V 用scause寄存器区分异常类型xv6kernel/riscv.h里有定义scause含义xv6 宏8(0x8)用户态ecall系统调用SCAUSE_ECALL13(0xd)读访问缺页load page faultSCAUSE_LOAD_PAGE_FAULT15(0xf)写访问缺页store/AMO page faultSCAUSE_STORE_PAGE_FAULT另外三个关键寄存器stval触发缺页的虚拟地址哪块内存没映射。sepc触发异常的那条用户指令地址返回时从这儿重来。satp当前页表的物理基址切换进程即切换satp。4. 地址空间、sz与uvmunmap每个 xv6 进程的地盘是一段连续虚拟地址[0, sz)sz是地址空间的上界堆顶。sbrk增长sz就是在扩大地盘。页表负责把[0, sz)里的虚拟地址映射到物理页。当进程退出exit或被exec替换时内核会调用uvmunmap(pagetable, 0, sz, 1)逐一解除[0, sz)的所有映射并释放物理页。记住这个调用——它正是本步panic的真凶。5. 本步改动范围文件改动kernel/sysproc.c唯一改动点改写sys_sbrk()删掉growproc()只改sz这一步不需要动Makefile、proc.h、页表代码——纯粹是sbrk语义的瘦身。实现思路整体数据流对比原版sys_sbrk→growproc(n)→uvmalloc立刻分配物理页 建映射 → 返回旧sz。本版lazy 第一步sys_sbrk→不分配只动sz→ 返回旧sz。关键设计点n 0扩大内存只做p-sz n不调用growproc。这就是lazy——地盘记大了但物理页一个都还没给。等到进程真去访问新地址才会触发缺页下一步的 handler 才去补分配。n 0缩小内存不能 lazy必须立刻回收。因为用户明确说我要还回这块内存内核得马上uvmdealloc释放物理页、解映射否则既泄漏内存又会让进程之后访问到已被回收的页。返回值和原版一致返回旧sz即新分配区的起始地址。官方 lab 原文让我们先预言后果Try to guess what the result of this modification will be: what will break?答案进程一旦访问到sbrk新记下来、却没映射的地址就会缺页而当下内核还没实现 lazy handler于是崩溃。这正是验证一节要看到的。代码实现kernel/sysproc.c—— 改写sys_sbrk/* * kernel/sysproc.c */uint64sys_sbrk(void){intaddr;intn;if(argint(0,n)0)return-1;addrmyproc()-sz;/* if(growproc(n) 0) return -1; */structproc*pmyproc();if(n0)p-szn;// 惰性分配仅改变 szelseif(p-szn0)// 如果是减少内存还是要马上执行要检查内存减少后大小是否大于 0p-szuvmdealloc(p-pagetable,p-sz,p-szn);elsereturn-1;returnaddr;}逐行理解addr myproc()-sz;先快照旧sz作为返回值新分配区起点。原growproc(n)被注释掉——这就是 lazy 的开关去掉它sbrk不再分配物理页。if (n 0) p-sz n;扩大时只记账不建映射。else if (p-sz n 0)缩小n0时p-sz n是缩小后的新上界先确认它 0不能把地址空间缩到 0 或负数然后uvmdealloc立即回收[新sz, 旧sz)这段物理页与映射。else return -1;n0且缩到非正拒绝并报错。return addr;返回旧sz语义与原版一致。验证按官方步骤启动 xv6在 shell 里敲一个最简单的命令$makeqemu$echohi usertrap(): unexpected scause 0x000000000000000fpid3sepc0x00000000000012acstval0x0000000000004008 panic: uvmunmap: not mapped这是预期的——本步还没写 lazy handler崩溃正好证明账记了、页没给。官方 lab 原文给的参考输出几乎一致仅sepc/stval具体数值因二进制略有差异usertrap(): unexpected scause 0x000000000000000f pid3 sepc0x0000000000001258 stval0x0000000000004008 va0x0000000000004000 pte0x0000000000000000 panic: uvmunmap: not mapped为什么是panic: uvmunmap: not mapped而不是直接页面错误退出这是本步最容易误解的地方把完整链路拆开触发缺页echo hi运行时shell或其子进程会通过sbrk申请堆比如malloc缓冲区。sys_sbrk只把sz记大没建映射。随后程序向新地址0x4008stval的值落在页[0x4000,0x5000)内做一次写访问 → MMU 发现该虚拟地址无有效 PTE → 触发store page faultscause 0xf。内核陷入usertrap()此时 lazy handler 还没写所以走usertrap的兜底else分支——打印usertrap(): unexpected scause 0xf...并把p-killed 1。注意此刻并没有 panic只是标记进程该死。进程被回收因killed返回用户态前内核会走exit()→freeproc()→uvmunmap(p-pagetable, 0, p-sz, 1)去解除[0, sz)全部映射。panic 在这里uvmunmap一路解映射走到sbrk新记大的那段[旧sz, 新sz)时发现这些虚拟地址从来没建过 PTE等于 0于是panic(uvmunmap: not mapped)。一句话总结缺页发生在访问时panic 发生在进程退出回收地址空间时。两者差着一个完整的kill → exit → freeproc → uvmunmap流程。理解这条链下一步往usertrap里插 lazy handler 时你就知道要在哪拦、拦下来干什么了。复盘本步解决了什么迈出了 lazy allocation 的第一步把申请即分配拆成了记账 延迟分配两个阶段。虽然本步还没真正分配但已经把sbrk的语义瘦身到位为下一步的缺页处理腾出了接口。亲手验证了一条崩溃链缺页scause0xf→usertrap兜底 →killed→exit/freeproc/uvmunmap→panic。这条链把 Lab4 学的 trap 流程异常 →usertrap→ 处理/杀进程和 Lab3 学的页表/地址空间sz、PTE、解映射串在了一起。与真实操作系统Linux的对比lazy / demand paging 不是 xv6 的玩具概念而是现代 OS 的标配Linux 的用户态堆brk/mmap、文件映射mmap、共享库加载默认都是按需调页——mmap只改 VMA虚拟内存区域真正缺页才分配物理页这叫minor fault若还需从磁盘读则是major fault。Linux 还有overcommit策略允许sbrk/mmap申请超过物理内存的虚额度赌你用不完——本质就是本步只记账不分配思想的极致版。后面 Lab6 的Copy-on-Write fork也是同一家族fork 时不真复制物理页等父子任一方写时才分配——lazy 思想一以贯之。收获demand paging / lazy allocation能讲清为什么不在申请时分配、延迟到访问时有什么好处快、省、支持稀疏是 OS 内存管理章节的高频题。page fault 全流程scause/stval/sepc三个寄存器各司其职缺页不是错误而是正常的中断信号内核 handler 负责补分配。sz与页表的关系sz只是账本上多大页表才是真正给了多少——二者解耦正是 lazy 的前提。为下一步铺路下一关Lazy allocation只需在usertrap里r_scause()13/15时用kalloc()mappages()在缺页地址补一页、清零、uvmunmap改成缺映射不 panic即可让echo hi跑通。回头看本步的 panic正是下一关要精准打击的目标。建议把前置知识里的scause编码表和验证里的崩溃链存下——它们会贯穿整个 Lab5甚至 Lab6 的 COW fork 也复用同一套缺页处理框架。
Eliminate allocation from sbrk() (easy)实验目标这是 Lab5Lazy page allocation惰性页分配的第一步也是整套按需分页大戏的序章。本步只做一件事从sbrk()系统调用里删掉真正的内存分配只记一笔我分配了多大的账。练习目标改写sys_sbrk()去掉growproc()调用仅让进程sz地址空间上界增长不建立任何物理映射。理解lazy allocation惰性/按需分配的核心思想内存不在sbrk时一次性分配而是等到进程真正访问那块地址、触发缺页时才分配。亲手观察这一步会引发什么崩溃想清楚崩溃的完整链路——这正是下一步真正实现 lazy handler要修的靶子。官方 lab 原文对这一步的定位非常清楚Your first task is to delete page allocation from thesbrk(n)system call implementation…sbrk(n)grows the process’s memory size bynbytes, and then returns the start of the newly allocated region (i.e., the old size). Your newsbrk(n)should just increment the process’s size (myproc()-sz) bynand return the old size.It should not allocate memory— so you should delete the call togrowproc()(but you still need to increase the process’s size!).前置知识1.sbrk与进程堆内存xv6的用户程序通过sbrk()向内核申请堆内存。官方 lab 原文定义得很直白Xv6 applications ask the kernel for heap memory using thesbrk()system call…sbrk(n)grows the process’s memory size bynbytes, and then returns the start of the newly allocated region (i.e., the old size).在标准 xv6 里sys_sbrk的核心是growproc(n)→uvmalloc()后者干两件事用kalloc()从空闲链表抠出一块物理内存用mappages()在页表里把新虚拟地址映射到这块物理页。也就是说传统实现是申请即分配——sbrk一调用物理页马上就位。2. 为什么要 lazy官方 lab 原文的思想内核One of the many neat tricks an O/S can play with page table hardware is lazy allocation of user-space heap memory… It can take a long time for a kernel to allocate and map memory for a large request. Consider, for example, that a gigabyte consists of 262,144 4096-byte pages… In addition,some programs allocate more memory than they actually use(e.g., to implement sparse arrays), or allocate memory well in advance of use. To allowsbrk()to complete more quickly in these cases, sophisticated kernels allocate user memorylazily. That is,sbrk()doesn’t allocate physical memory, but justremembers which user addresses are allocated and marks those addresses as invalid in the user page table. When the process first tries to use any given page of lazily-allocated memory, the CPU generates apage fault, which the kernel handles by allocating physical memory, zeroing it, and mapping it.这段话是整套 Lab5 的题眼提炼成三句话大请求慢1GB 要建 26 万个页表项逐个分配很贵。超额/提前分配普遍稀疏数组、预分配缓冲区大部分内存根本用不上。lazy 的做法sbrk只记账改sz 把对应页表项标记为无效第一次真正访问时才由缺页中断触发分配。这叫demand paging按需分页。3. RISC-V 缺页异常与scause编码进程访问一块未被映射的虚拟地址时MMU 硬件发现页表项无效 → CPU 触发页错误异常page fault陷入内核usertrap()。RISC-V 用scause寄存器区分异常类型xv6kernel/riscv.h里有定义scause含义xv6 宏8(0x8)用户态ecall系统调用SCAUSE_ECALL13(0xd)读访问缺页load page faultSCAUSE_LOAD_PAGE_FAULT15(0xf)写访问缺页store/AMO page faultSCAUSE_STORE_PAGE_FAULT另外三个关键寄存器stval触发缺页的虚拟地址哪块内存没映射。sepc触发异常的那条用户指令地址返回时从这儿重来。satp当前页表的物理基址切换进程即切换satp。4. 地址空间、sz与uvmunmap每个 xv6 进程的地盘是一段连续虚拟地址[0, sz)sz是地址空间的上界堆顶。sbrk增长sz就是在扩大地盘。页表负责把[0, sz)里的虚拟地址映射到物理页。当进程退出exit或被exec替换时内核会调用uvmunmap(pagetable, 0, sz, 1)逐一解除[0, sz)的所有映射并释放物理页。记住这个调用——它正是本步panic的真凶。5. 本步改动范围文件改动kernel/sysproc.c唯一改动点改写sys_sbrk()删掉growproc()只改sz这一步不需要动Makefile、proc.h、页表代码——纯粹是sbrk语义的瘦身。实现思路整体数据流对比原版sys_sbrk→growproc(n)→uvmalloc立刻分配物理页 建映射 → 返回旧sz。本版lazy 第一步sys_sbrk→不分配只动sz→ 返回旧sz。关键设计点n 0扩大内存只做p-sz n不调用growproc。这就是lazy——地盘记大了但物理页一个都还没给。等到进程真去访问新地址才会触发缺页下一步的 handler 才去补分配。n 0缩小内存不能 lazy必须立刻回收。因为用户明确说我要还回这块内存内核得马上uvmdealloc释放物理页、解映射否则既泄漏内存又会让进程之后访问到已被回收的页。返回值和原版一致返回旧sz即新分配区的起始地址。官方 lab 原文让我们先预言后果Try to guess what the result of this modification will be: what will break?答案进程一旦访问到sbrk新记下来、却没映射的地址就会缺页而当下内核还没实现 lazy handler于是崩溃。这正是验证一节要看到的。代码实现kernel/sysproc.c—— 改写sys_sbrk/* * kernel/sysproc.c */uint64sys_sbrk(void){intaddr;intn;if(argint(0,n)0)return-1;addrmyproc()-sz;/* if(growproc(n) 0) return -1; */structproc*pmyproc();if(n0)p-szn;// 惰性分配仅改变 szelseif(p-szn0)// 如果是减少内存还是要马上执行要检查内存减少后大小是否大于 0p-szuvmdealloc(p-pagetable,p-sz,p-szn);elsereturn-1;returnaddr;}逐行理解addr myproc()-sz;先快照旧sz作为返回值新分配区起点。原growproc(n)被注释掉——这就是 lazy 的开关去掉它sbrk不再分配物理页。if (n 0) p-sz n;扩大时只记账不建映射。else if (p-sz n 0)缩小n0时p-sz n是缩小后的新上界先确认它 0不能把地址空间缩到 0 或负数然后uvmdealloc立即回收[新sz, 旧sz)这段物理页与映射。else return -1;n0且缩到非正拒绝并报错。return addr;返回旧sz语义与原版一致。验证按官方步骤启动 xv6在 shell 里敲一个最简单的命令$makeqemu$echohi usertrap(): unexpected scause 0x000000000000000fpid3sepc0x00000000000012acstval0x0000000000004008 panic: uvmunmap: not mapped这是预期的——本步还没写 lazy handler崩溃正好证明账记了、页没给。官方 lab 原文给的参考输出几乎一致仅sepc/stval具体数值因二进制略有差异usertrap(): unexpected scause 0x000000000000000f pid3 sepc0x0000000000001258 stval0x0000000000004008 va0x0000000000004000 pte0x0000000000000000 panic: uvmunmap: not mapped为什么是panic: uvmunmap: not mapped而不是直接页面错误退出这是本步最容易误解的地方把完整链路拆开触发缺页echo hi运行时shell或其子进程会通过sbrk申请堆比如malloc缓冲区。sys_sbrk只把sz记大没建映射。随后程序向新地址0x4008stval的值落在页[0x4000,0x5000)内做一次写访问 → MMU 发现该虚拟地址无有效 PTE → 触发store page faultscause 0xf。内核陷入usertrap()此时 lazy handler 还没写所以走usertrap的兜底else分支——打印usertrap(): unexpected scause 0xf...并把p-killed 1。注意此刻并没有 panic只是标记进程该死。进程被回收因killed返回用户态前内核会走exit()→freeproc()→uvmunmap(p-pagetable, 0, p-sz, 1)去解除[0, sz)全部映射。panic 在这里uvmunmap一路解映射走到sbrk新记大的那段[旧sz, 新sz)时发现这些虚拟地址从来没建过 PTE等于 0于是panic(uvmunmap: not mapped)。一句话总结缺页发生在访问时panic 发生在进程退出回收地址空间时。两者差着一个完整的kill → exit → freeproc → uvmunmap流程。理解这条链下一步往usertrap里插 lazy handler 时你就知道要在哪拦、拦下来干什么了。复盘本步解决了什么迈出了 lazy allocation 的第一步把申请即分配拆成了记账 延迟分配两个阶段。虽然本步还没真正分配但已经把sbrk的语义瘦身到位为下一步的缺页处理腾出了接口。亲手验证了一条崩溃链缺页scause0xf→usertrap兜底 →killed→exit/freeproc/uvmunmap→panic。这条链把 Lab4 学的 trap 流程异常 →usertrap→ 处理/杀进程和 Lab3 学的页表/地址空间sz、PTE、解映射串在了一起。与真实操作系统Linux的对比lazy / demand paging 不是 xv6 的玩具概念而是现代 OS 的标配Linux 的用户态堆brk/mmap、文件映射mmap、共享库加载默认都是按需调页——mmap只改 VMA虚拟内存区域真正缺页才分配物理页这叫minor fault若还需从磁盘读则是major fault。Linux 还有overcommit策略允许sbrk/mmap申请超过物理内存的虚额度赌你用不完——本质就是本步只记账不分配思想的极致版。后面 Lab6 的Copy-on-Write fork也是同一家族fork 时不真复制物理页等父子任一方写时才分配——lazy 思想一以贯之。收获demand paging / lazy allocation能讲清为什么不在申请时分配、延迟到访问时有什么好处快、省、支持稀疏是 OS 内存管理章节的高频题。page fault 全流程scause/stval/sepc三个寄存器各司其职缺页不是错误而是正常的中断信号内核 handler 负责补分配。sz与页表的关系sz只是账本上多大页表才是真正给了多少——二者解耦正是 lazy 的前提。为下一步铺路下一关Lazy allocation只需在usertrap里r_scause()13/15时用kalloc()mappages()在缺页地址补一页、清零、uvmunmap改成缺映射不 panic即可让echo hi跑通。回头看本步的 panic正是下一关要精准打击的目标。建议把前置知识里的scause编码表和验证里的崩溃链存下——它们会贯穿整个 Lab5甚至 Lab6 的 COW fork 也复用同一套缺页处理框架。
