链接地址与维护堆边：三个可分开复算的任务
这份任务包含三台独立状态机：对象链接、精确引用计数、双代停止世界回收。每台都有固定输入、正常轨迹和一个使结论失败的变体；它们不共用未声明的“地址”“根”或“计数”含义。先任选一个任务做完，再用另两题检验相邻机制的边界。
下载标准库检查器及固定运行证据。运行方式为 python foundations-cs03b-checker.py --trace --out result.json，或用 python -O foundations-cs03b-checker.py 关闭日志并检查显式验证不会被优化掉。
任务一：双对象地址、补丁与执行目标
入口自测：对齐向上取整怎样计算？同名局部符号能否存在于两个文件？PC相对字段中的 P 指哪个地址？答案分别是 (cursor+a−1)//a*a（a为正二次幂）、可以且以对象身份区分、由每种 relocation 约定，本题明确是字段地址。
链接任务的补课入口是数组和整数；运行时两题先复习根与可达性及复制回收。这些是可跳回的机制接口，不要求先读抽象解释或整套操作系统。
教学对象格式使用32位字节地址、小端，只有 local 和唯一 strong-global 符号。text 区域从0x1000开始，data从0x2000开始，按A、B顺序布置。初始节字节全零，只检验补丁字段与教学CALL目标，不把全零操作码镜像当成主机可执行文件。
| 对象 | text 大小/对齐 | data 大小/对齐 | 定义 |
|---|---|---|---|
| A | 12/4 | 8/8 | main=global text+0；scratch=local data+4 |
| B | 8/8 | 8/8 | inc=global text+0；counter=global data+0；scratch=local data+4 |
重定位为：A.text+2 的 PCREL16 指 inc，加数−2；A.data+0 的 ABS32 指 counter，加数4；B.text+2 的 PCREL16 指 main，加数−2。ABS32写S+A，PCREL16写S+A−P。CALL长度4，位移字段从pc+2开始，执行目标为pc+4+disp。
完整答案：A.text=0x1000，B.text=0x1010，中间4字节填充；A.data=0x2000，B.data=0x2008。global地址为main=0x1000、inc=0x1010、counter=0x2008；local地址为A.scratch=0x2004、B.scratch=0x200c。三补丁依次为12的0c 00、0x200c的0c 20 00 00、−20的ec ff。两次单步目标分别为0x1010、0x1000；两条互相CALL不构成正常终止示例。
把第一条加数错误改成0，补丁变14，目标变0x1012，落入指令内部。把B.text对齐改成0x10000，inc放在0x10000，第一条有符号16位位移越界，整个链接应在应用任何补丁前失败。先截低16位再声称成功不合规格。
迁移一：所有区域共同平移0x3000，PCREL16仍12和−20，ABS32变0x500c。迁移二：A.text变20字节、B.text按16字节对齐，B到0x1020，双向位移28和−36。迁移三：增加第二份global main必须报重复定义；保留两份local scratch合法。每个失败都要证明输入字节与已发布镜像未被修改。
静态链接完成的地址仍须与装载位置一致。按重定位页的eager扩展，导入inc若在运行时解析到0x7010，应在入口启动前把导入指针槽写0x7010，再由间接调用读取。这里没有真实ELF解析、共享库搜寻、PLT延迟绑定或系统loader测试；这些范围没有被“链接器检查通过”一语代替。
任务二：槽计数、级联释放与环
使用引用计数页的单线程模型。根r指P；P.a、P.b都指C；根t也指C。所有临时外部引用已经登记，普通整数对象ID不允许给mutator凭空恢复引用。
初始 rc(P)=1, rc(C)=3。清r后P变0入队，C仍3，因为待释放P的字段还存在。处理P时两条边分别使C降为2、1，再移除P；清t使C变0入队，处理C后堆为空。必须记录两条不同字段，而不是把同端点边去重。
只有t指C时，执行t=t应保持计数1、队列空。先release再retain会可能在零计数处释放C；简单延迟释放但不撤销队列也不安全。检查器正确路径先检查同值，再先retain新值、后release旧值。
另造根r→X、X.next→Y、Y.next→X。给Y的初始化临时根释放后，X计数2、Y计数1；再清r，二者都是1、队列空，而全根可达集合为空。普通RC留下这个环；标记清扫可在完整根图上释放它。不能把RC留下的两个对象误报成“仍被程序持有”。
迁移：无根自环也保持计数1；从无根环再指出尾链Z→W，尾链也可能被留住。若合法根仍持有X，可先断开Y.next再清根，级联将清空组件；失去全部根后，不能拿显示的X整数ID再执行断环。检查器的 replace 是受信任堆测试接口，只验证已分配身份、槽和计数，并不提供不可伪造能力系统；能力合法性是测试调用者的前置条件。
失败测试把max_count设为1，r已指C时尝试让s也指C，必须拒绝且s仍为空、rc(C)仍1。合法路径的validate重新数全图槽检查计数与零队列；这项全图核验单列成本，不是每次引用赋值的常数快速路径。
任务三：minor 回收不能遗漏老→幼入口
独立重置堆，不使用任务二的rc。老对象O@800有一个指针字段p，根r指O。幼对象A@104、B@120、U@136，各为一个头加一个指针字段，共16字节，均按8字节对齐；A.next=B，B.next=null，U.next=null。目标幼区从200开始、容量48字节。执行O.p=A时屏障记录槽M={(800,0)}。
minor先看根r，它是老指针不搬；再看M的O.p，复制A到200并把O.p改成200；扫描A′复制B到216；B′结束扫描。最终幼堆32字节，A′.next=216，U死亡，老O仍在800；M必须保留O.p。根r从未直接指幼对象，若没有M入口就无法发现A、B。
故意用 barrier=False 写O.p，再执行minor。它产生空幼堆，O.p却保留旧址104；之后完整状态验证报告悬空指针。这是受控错误注入，不是合法写入API选项。失败责任在写屏障，而不是根r或Cheney的唯一转发映射。
变体一：把目标容量降到16，只够A不够B。检查器在私有目标堆中发现不足，原老字段、根、幼堆与M全不变。真实原地转发实现没有这份免费回滚，若未预留空间，需要自己的失败协议。
变体二：第二轮前令O.p=null，M可暂时留旧条目；第二轮在304开始的空目标区收集后，幼堆为空，M清空。变体三：再增加O.q=A，两槽最终都指200，仍只复制32字节。变体四：一个不可达老D指U且其槽登记，minor会额外保留U，复制量48字节；这属于允许的保守保留。
提升测试将A@104从幼集合移入老集合，保持这个教学对象的地址身份，B@120仍幼。新M必须含A.next，即(104,0)。随后minor将B搬到200并把老A.next改200；仅保留原O.p槽不够，因为它现在指老A，minor不会沿老对象继续搜索。真实提升若同时搬址，还须额外完成所有引用更新，本测试不包含那个搬址过程。
成本账本、完成条件与来源
链接教具的重叠预检先排序q个节区间，成本O(q log q)；符号与补丁核心期望O(s+r)，字节拷贝另计。输出image是稀疏地址字典，存36个节字节；text区域跨度24、data跨度16，总跨度40包含4字节对齐填充。普通“拼接后文件大小”不能拿36或40中任意一个不加解释地代替。
RC的核心计数维护、回收边扫描、全图validate及事件日志分别计量。minor的kernel只枚举根、M和幼活集，但防御性输入校验及目标区间不重叠检查仍扫描全堆；preflight字段与排序开销单列。关闭trace后不会保留逐步历史；开启后日志消耗依事件数增长。
完成条件是三个任务分别闭合自己的不变量，正常结果、错误变体、失败原子性和迁移答案均能复算。没有把输入不变的失败测试称为生产运行时容错，也没有把若干有限图测试称为任意堆正确性证明。
规范和原始教材位置分别在符号与重定位、引用计数及分代屏障页列明。已有复制回收、根映射与闭包返回后移动回收终点继续承担完整根与移动别名接口，本任务不替换它们。