最近想试试把 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 -MP

ARMv8 前置

  • 高 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传递给它

CS140-Synchronization2

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 中的锁机制](
Last modification：September 12, 2022
© Allow specification reprint
如果觉得我的文章对你有用，请随意赞赏