XV6是怎么运行的

在真实的物理环境中。涉及到从硬件加电或重置到操作系统完全接管控制的过程。

这个过程大概分为以下几个步骤：

  1. 引导加载程序。 BIOS初始化硬件，找到设备，执行硬盘引导扇区的初始化代码。
  2. 引导加载程序加载内核。 引导加载程序读取磁盘上的内核映像到内存中，并跳转到内核的入口点开始执行。
  3. 内核初始化。设置中断描述符表，建立虚拟内存。在xv6中，这部分逻辑开始于main函数，该函数定义在kernel/main.c中。
  4. 启动进程。 创世纪进程init

kernel/main.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// start() jumps here in supervisor mode on all CPUs.
void
main()
{
  if(cpuid() == 0){ // 这个条件判断确保只有一个CPU（通常是CPU 0）执行以下的初始化任务，因为在多核系统中，所有的CPU核心几乎同时启动，但系统初始化只需执行一次。
    consoleinit();
    printfinit();
    printf("\n");
    printf("xv6 kernel is booting\n");
    printf("\n");
    kinit();         // physical page allocator
    kvminit();       // create kernel page table
    kvminithart();   // turn on paging
    procinit();      // process table
    trapinit();      // trap vectors
    trapinithart();  // install kernel trap vector
    plicinit();      // set up interrupt controller
    plicinithart();  // ask PLIC for device interrupts
    binit();         // buffer cache
    iinit();         // inode table
    fileinit();      // file table
    virtio_disk_init(); // emulated hard disk
    userinit();      // first user process
    __sync_synchronize();
    started = 1;
  } else {
    while(started == 0)
      ;
    __sync_synchronize();
    printf("hart %d starting\n", cpuid());
    kvminithart();    // turn on paging
    trapinithart();   // install kernel trap vector
    plicinithart();   // ask PLIC for device interrupts
  }

  scheduler();        
}

printf是如何执行的：简单来说，将待输出字符转换成字符流，写入内存缓冲区，调用驱动输出到控制台(或指定的输出设备、文件)

物理内存的初始化

1
2
3
4
5
6
7
8
void
freerange(void *pa_start, void *pa_end)
{
  char *p;
  p = (char*)PGROUNDUP((uint64)pa_start);
  for(; p + PGSIZE <= (char*)pa_end; p += PGSIZE)
    kfree(p);
}

在这部分代码中，从内存的下界到内存的上界，调用kfree函数释放内存页，使其可以被重新分配和使用。

内核页表初始化

1
2
3
4
5
6
7
8
9
// add a mapping to the kernel page table.
// only used when booting.
// does not flush TLB or enable paging.
void
kvmmap(pagetable_t kpgtbl, uint64 va, uint64 pa, uint64 sz, int perm)
{
  if(mappages(kpgtbl, va, sz, pa, perm) != 0)
    panic("kvmmap");
}

kvmmap函数在xv6操作系统中用于在内核的页表中添加一个新的虚拟地址到物理地址的映射。

  • pagetable_t kpgtbl: 这是一个页表的指针，指向当前的内核页表。在xv6中，页表用于存储虚拟地址到物理地址的映射信息。
  • uint64 va: 虚拟地址（Virtual Address），这是要添加映射的虚拟内存地址。
  • uint64 pa: 物理地址（Physical Address），这是va参数所指定的虚拟地址对应的物理内存地址。
  • uint64 sz: 映射区域的大小，单位是字节。这个参数指定了从va开始，需要映射多大的内存区域到物理地址pa。
  • int perm: 映射的权限设置，这些权限包括读（PTE_R）、写（PTE_W）和执行（PTE_X）。权限参数决定了CPU如何访问映射的内存区域，例如，一个只读的内存区域会阻止写入操作。

内核页表初始化的函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// Make a direct-map page table for the kernel.
pagetable_t
kvmmake(void)
{
  pagetable_t kpgtbl;

  kpgtbl = (pagetable_t) kalloc();
  memset(kpgtbl, 0, PGSIZE);

  // uart registers UART（通用异步接收器/发送器，一种常用的串行通信设备）
  kvmmap(kpgtbl, UART0, UART0, PGSIZE, PTE_R | PTE_W);

  // virtio mmio disk interface virtio磁盘接口（一种I/O虚拟化框架）的MMIO（Memory-Mapped I/O）
  kvmmap(kpgtbl, VIRTIO0, VIRTIO0, PGSIZE, PTE_R | PTE_W);

  // PLIC 平台级中断控制器（PLIC）
  kvmmap(kpgtbl, PLIC, PLIC, 0x400000, PTE_R | PTE_W);
 
  // map kernel text executable and read-only. 内核的可执行文本
  kvmmap(kpgtbl, KERNBASE, KERNBASE, (uint64)etext-KERNBASE, PTE_R | PTE_X);

  // map kernel data and the physical RAM we'll make use of. 内核数据及其后的物理内存区域
  kvmmap(kpgtbl, (uint64)etext, (uint64)etext, PHYSTOP-(uint64)etext, PTE_R | PTE_W);

  // map the trampoline for trap entry/exit to 中断入口/出口的trampoline代码映射了一个页面，它位于内核的最高虚拟地址。
  // the highest virtual address in the kernel.
  kvmmap(kpgtbl, TRAMPOLINE, (uint64)trampoline, PGSIZE, PTE_R | PTE_X);

  // map kernel stacks
  proc_mapstacks(kpgtbl);
  
  return kpgtbl;
}

进程表初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
// initialize the proc table at boot time.
void
procinit(void)
{
  struct proc *p;
  
  initlock(&pid_lock, "nextpid");
  initlock(&wait_lock, "wait_lock");
  for(p = proc; p < &proc[NPROC]; p++) {
      initlock(&p->lock, "proc");
      p->kstack = KSTACK((int) (p - proc));
  }
}

为每个进程分配一个锁和一个栈。

初始化中断设置

设置中断向量和中断处理程序

初始化文件系统

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# kernel/file.h
// in-memory copy of an inode
struct inode {
  uint dev;           // Device number
  uint inum;          // Inode number
  int ref;            // Reference count
  struct sleeplock lock; // protects everything below here
  int valid;          // inode has been read from disk?

  short type;         // copy of disk inode
  short major;
  short minor;
  short nlink;
  uint size;
  uint addrs[NDIRECT+1];
};

----------
# inode kernel/fs.c
struct {
  struct spinlock lock;
  struct inode inode[NINODE];
} itable;

void
iinit()
{
  int i = 0;
  
  initlock(&itable.lock, "itable");
  for(i = 0; i < NINODE; i++) {
    initsleeplock(&itable.inode[i].lock, "inode");
  }
}

inode表中有一个锁和一个inode列表，初始化inode表为每个节点分配一个锁。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# kernel/file.h
struct file {
  enum { FD_NONE, FD_PIPE, FD_INODE, FD_DEVICE } type;
  int ref; // reference count
  char readable;
  char writable;
  struct pipe *pipe; // FD_PIPE
  struct inode *ip;  // FD_INODE and FD_DEVICE
  uint off;          // FD_INODE
  short major;       // FD_DEVICE
};
-----------------------
struct devsw devsw[NDEV];
struct {
  struct spinlock lock;
  struct file file[NFILE];
} ftable;

void
fileinit(void)
{
  initlock(&ftable.lock, "ftable");
}

类似于inode表，分配锁。

创建第一个用户进程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// Set up first user process.
void
userinit(void)
{
  struct proc *p;

  p = allocproc();
  initproc = p;
  
  // allocate one user page and copy init's instructions
  // and data into it.
  uvminit(p->pagetable, initcode, sizeof(initcode));
  p->sz = PGSIZE;

  // prepare for the very first "return" from kernel to user.
  p->trapframe->epc = 0;      // user program counter
  p->trapframe->sp = PGSIZE;  // user stack pointer

  safestrcpy(p->name, "initcode", sizeof(p->name));
  p->cwd = namei("/");

  p->state = RUNNABLE;

  release(&p->lock);
}
  1. 设置进程的初始内存映射
  2. 设置进程的初始大小
  3. 准备从内核返回到用户空间

Multithreading

阅读源码

数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# user/uthread.c
/* Possible states of a thread: */
#define FREE 0x0
#define RUNNING 0x1
#define RUNNABLE 0x2

#define STACK_SIZE 8192
#define MAX_THREAD 4

struct thread
{
  char stack[STACK_SIZE]; /* the thread's stack */
  int state;              /* FREE, RUNNING, RUNNABLE */
};
struct thread all_thread[MAX_THREAD];
struct thread *current_thread;
extern void thread_switch(uint64, uint64);

包括线程状态，线程的结构体，线程组，当前线程，线程切换。

初始化

设置current_thread为第一个线程。

调度

遍历所有线程，寻找一个状态为RUNNABLE的线程作为next_thread，然后通过调用thread_switch函数来切换到这个线程执行。

创建

在all_thread数组中找到一个状态为FREE的线程结构，然后将其状态设置为RUNNABLE，并初始化它的栈和执行函数。

让出CPU

这个函数允许当前线程主动放弃CPU，将自己的状态设置为RUNNABLE并调用thread_schedule来重新调度。

线程编程

  1. 参考kernel/switch.S代码，完成用户态线程切换汇编代码
  2. 给thread结构体添加context
  3. 线程创建时，为context,stack分配内存，state设置成runable
  4. 线程切换，调用汇编程序

解决哈希表的race

多线程情况下存在race condition。改善这个hashtable.

为每个bucket配置一个pthread_mutex锁来保证只有一个线程可以读这个bucket里的所有数据进行读和写的操作即可.

barrier

每个线程都会呼叫barrier()函数, 将会卡在里面直到每个需要synchronize的线程都进入这个函数. 需要使用conditional variable来实现等待和唤醒的功能.

networking

transmit

e1000_transmit是给了一个新的packet, 我们需要在ring里找到下一个空余位置, 然后把它放进去等待传输.

recieve

e1000_recv是需要遍历这个ring, 把所有新到来的packet交由网络上层的协议/应用去处理.

locks

memory allocator

数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# kernel/kalloc.c

struct {
  struct spinlock lock;
  struct run *freelist;
} kmem[NCPU];

void
kinit()
{
  for (int i = 0; i < NCPU; i++) {
    char name[9] = {0};
    snprintf(name, 8, "kmem-%d", i);
    initlock(&kmem[i].lock, name);
  }
  freerange(end, (void*)PHYSTOP);
}

为每一个cpu核维系一个freelist空闲内存页链表, 只有在本核的内存不够时, 才试图去偷取别的核的内存.

buffer cache

这个实验其实和上一个memory allocator很类似, 主打一个”回收利用”的思想. xv6会缓存一些经常使用的block块在内存里(即这个buffer cache pool), 使得每次重复调用这个block块时直接从内存读取, 而不用做磁盘I/O.

原始版本的buffer cache由一个大锁bcache.lock保护, 限制了并行运行的效率. 我们要把它拆解为更精细的锁管理, 用hash bucket的思想. 并且放弃双链表的管理方式, 直接使用ticks时间戳来实现LRU(least-recently-used)算法.

fs

large files

img

双层映射，取余数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
if (bn < NINDIRECT2)
{
  if ((addr = ip->addrs[NDIRECT + 1]) == 0)
    ip->addrs[NDIRECT] = addr = balloc(ip->dev);
  bp = bread(ip->dev, addr);
  a = (uint *)bp->data;
  if ((addr = a[bn / NINDIRECT]) == 0)
  { // 之后的每一个映射可以吃下NINDIRECT个blocks
    a[bn / NINDIRECT] = addr = balloc(ip->dev);
    log_write(bp);
  }
  brelse(bp);

  // Load the 2nd indirect block, allocating if necessary
  bp2 = bread(ip->dev, addr);
  b = (uint *)bp2->data;
  if ((addr = b[bn % NINDIRECT]) == 0)
  { // 取余数
    b[bn % NINDIRECT] = addr = balloc(ip->dev);
    log_write(bp2);
  }
  brelse(bp2);
  return addr;
}

软链接

设置inode的type为T_SYMLINK，在data里记录target的path。

打开一个软链接类型的文件时，需要递归寻址，设置最大递归深度以防止陷入死循环。