WIP
最近想试试把 xv6 移植到 arm 上，正好看到了 fdu 的 os 实验是这个的改编
看上去不错，做一下
Makefile
以下几个需关掉:
- PIE: Position-Independent Executable，可防止
return-to-libc攻击 - PIC: Position-Independent Code，共享库，防止覆盖
- startfiles: 初始化 SP，static data，后跳转至 main
打开:
- general-regs-only: 防止 ARM 使用
NEON寄存器，增加代码复杂度 - -MMD -MP: 生成
.d文件
CFLAGS := -Wall -g -O2 \
-fno-pie -fno-pic -fno-stack-protector \
-static -fno-builtin -nostdlib -ffreestanding -nostartfiles \
-mgeneral-regs-only \
-MMD -MPARMv8 前置
- 高 16 位用于区分使用哪个页表 (0xFFFF:
TTBR_EL1, 0x0000:TTBR_EL0) - TLB 查询在 L1 Cache 未命中后，TLB 未命中则在内存中
Walk Table - 页表支持：至少两级，至多四级
- 页表分级：Global Upper Middle Entry（PGD, PUD, PMD, PTE）
启动流程
树莓派特有的从 GPU 启动
- linker.ld 确认代码布局，将
entry.S中的__start放在BootLoader跳转地址0xffff000000080000 kpgdir.c中硬编码页表，以便开MMU后地址正确- GPU 初始化硬件，跳转至
__start(armstub8.S) __start逐步降至EL1后，根据MPIDR_EL1不同，设置不同页表与SP，开MMU，跳转至main- 清空
BSS， 初始化console、uart - 初始化内存分配器，将
.bss后至PHYSTOP间内存加入kmem - 中断初始化
- 用
lvbar(load vbar) 加载kern/vectors.S配置的中断向量
中断处理
- 中断后自动关中断，这意味着所有的中断只会在用户态发生，即只有从 EL0 到 EL1 的中断
- 根据不同的中断种类，跳到中断向量表中的不同位置
- 保存中断前的 PSTATE 至 SPSR_EL1，保存中断前的 PC 到 ELR_EL1，保存中断原因信息到 ESR_EL1
- 将栈指针 sp 从 SP_EL0 换为 SP_EL1，这也意味着 SPSEL_EL1 的值为 1
中断发生时 CPU 的操作
- 查询 EL0 中断向量表 (vector.S)
- ARMv8 存在四种中断类型，这里只处理前两种
- el0_aarch64 上的
Synchronous与IRQ中断，路由至alltraps(trapasm.S) - (其他类型 将类型路由至
irq_error
alltraps (asm func)
保存现场至
struct *trapframe(- 通用寄存器: x0 - x30 (内核中断非函数调用，需全部保存)
- 中断信息 (避免多级中断丢失): SPSR_EL1 (PSTATE), ELR_EL1 (PC), SP_EL0 (SP)
- cpu: 中断发生在的 cpu 结构 (*)
- proc: 当前进程 PCB (*)
- 调用
trap(trapframe)(trap.c) - 注意压参与弹参顺序，跳转使用 bl 以便返回 (直接 branch 跳不回来，bl 会将当前 pc -> lr)
/* vectors.S send all traps here. */
.global alltraps
alltraps:
stp x29, x30, [sp, #-16]!
stp x27, x28, [sp, #-16]!
stp x25, x26, [sp, #-16]!
stp x23, x24, [sp, #-16]!
stp x21, x22, [sp, #-16]!
stp x19, x20, [sp, #-16]!
stp x17, x18, [sp, #-16]!
stp x15, x16, [sp, #-16]!
stp x13, x14, [sp, #-16]!
stp x11, x12, [sp, #-16]!
stp x9, x10, [sp, #-16]!
stp x7, x8, [sp, #-16]!
stp x5, x6, [sp, #-16]!
stp x3, x4, [sp, #-16]!
stp x1, x2, [sp, #-16]!
mrs x1, spsr_el1 // sp
mrs x2, elr_el1 // pc
mrs x3, sp_el0 // pstate
stp x1, x0, [sp, #-16]!
stp x3, x2, [sp, #-16]!
add x0, sp, #0
bl trap
.global trapret
trapret:
ldp x0, x1, [sp], #16
msr elr_el1, x1
msr spsr_el1, x0
ldp x2, x0, [sp], #16
msr sp_el0, x2
ldp x1, x2, [sp], #16
ldp x3, x4, [sp], #16
ldp x5, x6, [sp], #16
ldp x7, x8, [sp], #16
ldp x9, x10, [sp], #16
ldp x11, x12, [sp], #16
ldp x13, x14, [sp], #16
ldp x15, x16, [sp], #16
ldp x17, x18, [sp], #16
ldp x19, x20, [sp], #16
ldp x21, x22, [sp], #16
ldp x23, x24, [sp], #16
ldp x25, x26, [sp], #16
ldp x27, x28, [sp], #16
ldp x29, x30, [sp], #16
eret原子操作
- Atomic Exchange (test and set)
- FAA (fetch and add)
- CAS (compare and swap)
SpinLock
struct spinlock {
int locked;
};
void spin_lock(struct spinlock *lk)
{
while (test_and_set(lk->locked, 1)) ;
}
void spin_unlock(struct spinlock *lk)
{
test_and_set(lk->locked, 0);
}TicketLock
所有 cpu 都在等待 lk->turn, cpu 数较多时，需要修改全部 cache 性能较差
线程锁，保证多线程资源访问顺序一致性
struct ticketlock {
int ticket, turn;
};
void ticket_lock(struct ticketlock *lk)
{
int t = fetch_and_add(lk->ticket, 1);
while (lk->turn != t) ;
}
void ticket_unlock(struct ticketlock *lk)
{
lk-turn++;
}MCSLock
基于队列，对多核的缓存较友好，效率较高
MCS lock可以解决在锁的争用比较激烈的场景下，cache line 无谓刷新的问题，但它内含一个指针，所以更消耗存储空间，但这个指针又是不可或缺的，因为正是依靠这个指针，持有spinlock的CPU才能找到等待队列中的下一个节点，将spinlock传递给它
struct mcslock {
struct mcslock *next;
int locked;
};
void mcs_lock(struct mcslock *lk, struct mcslock *i)
{
i->next = i->locked = 0;
struct mcslock *pre = test_and_set(&lk->next, i);
if (pre) {
i->locked = 1;
pre->next = i;
}
while (i->locked) ;
}
void mcs_unlock(struct mcslock *lk, struct mcslock *i)
{
if (i->next == 0)
if (compare_and_swap(&lk->next, i, 0) == i)
return;
while (i->next == 0) ;
i->next->locked = 0;
}qspinlock
MCSLock 改进
WIP
读写锁
struct rwlock {
struct spinlock r, w; /* Or mutex. */
int cnt; /* Number of readers. */
};
void read_lock(struct rwlock *lk)
{
acquire(&lk->r);
if (lk->cnt++ == 0)
acquire(&lk->w);
release(&lk->r);
}
void read_unlock(struct rwlock *lk)
{
acquire(&lk->r);
if (--lk->cnt == 0)
release(&lk-w);
release(&lk->r);
}
void write_lock(struct rwlock *lk)
{
acquire(&lk->w);
}
void write_unlock(struct rwlock *lk)
{
release(&lk->w);
}信号量
struct semaphore {
/* If cnt < 0, -cnt indicates the number of waiters. */
int cnt;
struct spinlock lk;
};
void sem_init(struct semaphore *s, int cnt)
{
s->cnt = cnt;
}
void sem_wait(struct semaphore *s)
{
acquire(&s->lk);
if (--s->cnt < 0)
sleep(s, &s->lk); /* Sleep on s. */
release(&s->lk);
}
void sem_signal(struct semaphore *s)
{
acquire(&s->lk);
if (s->cnt++ < 0)
wakeup1(s); /* Wake up one process sleeping on s. */
release(&s->lk);
}Question
vm_free实现存疑 (xv6)
Reference
MISC
Interrupt
Lock
- [Linux 中的锁机制](