OS-进程调度lab(mit6.828 lab4)

void
lapic_init(void){
	// lapicaddr is the physical address of the LAPIC's 4K MMIO
	// region.  Map it in to virtual memory so we can access it.
	lapic = mmio_map_region(lapicaddr, 4096);
}

// Reserve size bytes in the MMIO region and map [pa,pa+size) at this
// location.  Return the base of the reserved region.  size does *not*
// have to be multiple of PGSIZE.

void *
mmio_map_region(physaddr_t pa, size_t size)
{
	// Where to start the next region.  Initially, this is the beginning of the MMIO region.
	// Because this is static, its value will be preserved between calls to mmio_map_region (just like nextfree in boot_alloc).
    // MMIO区域的基地址
	static uintptr_t base = MMIOBASE;

	// 从基地址起保留size大小的虚拟内存，并把物理内存[pa,pa+size)映射到虚拟内存[base,base+size)
	// Reserve size bytes of virtual memory starting at base and map physical pages [pa,pa+size) to virtual addresses [base,base+size).  
	// Since this is device memory and not regular DRAM, you'll have to tell the CPU that it isn't safe to cache access to this memory.  
	// Luckily, the page tables provide bits for this purpose; simply create the mapping with PTE_PCD|PTE_PWT (cache-disable and write-through) in addition to PTE_W.  (If you're interested in more details on this, see section 10.5 of IA32 volume 3A.)
	//
	// Be sure to round size up to a multiple of PGSIZE and to handle if this reservation would overflow MMIOLIM (it's okay to simply panic if this happens).
	//
	// Hint: The staff solution uses boot_map_region.
	//
	// Your code here:
    
	// 得到对应的物理页，传入的物理地址和size不一定正好是一页
    // 为了使得物理页地址对齐，只有对齐了地址才能使用boot_map_region()函数进行映射
	size = ROUNDUP(pa + size, PGSIZE);	//物理页起始
	pa = ROUNDDOWN(pa, PGSIZE);		//物理页结束
	size -= pa;	//物理页大小
    // 不能overflow MMIOLIM，如果超过了[MMIOBASE, MMIOBASE+4M)，直接panic报错
	if (base + size >= MMIOLIM)
		panic("not enough memory");
    // 将一段虚拟内存[base, base+size)映射到同样长度的物理内存[pa, pa+size)
	boot_map_region(kern_pgdir, base, size, pa, PTE_PCD | PTE_PWT | PTE_W);
    // 更改可用的MMIO区域的基地址，因为base是static，需要维护
	base += size;
	return (void *)(base - size);	//返回一开始MMIO区域的基地址，即如今lapic的起始地址
}

//
// Map [va, va+size) of virtual address space to physical [pa, pa+size) in the page table rooted at pgdir.
// Size is a multiple of PGSIZE, and va and pa are both page-aligned.
// Use permission bits perm|PTE_P for the entries.
//
// This function is only intended to set up the ``static'' mappings above UTOP.
// As such, it should *not* change the pp_ref field on the mapped pages.
//
// Hint: the TA solution uses pgdir_walk
static void
boot_map_region(pde_t *pgdir, uintptr_t va, size_t size, physaddr_t pa, int perm)
{
	// Fill this function in
	size_t pgs = size / PGSIZE;
	if (size % PGSIZE != 0)
	{
		pgs++;
	}
	for (int i = 0; i < pgs; i++)
	{
         // pgdir_walk()的作用是根据pgdir和va返回对应的page table entry的指针
		pte_t *pte = pgdir_walk(pgdir, (void *)va, 1);
		if (pte == NULL)
		{
			panic("boot_map_region(): out of memory\n");
		}
         // 更新pte信息，因为pa已经对齐，所以pa低12位为0
         // 入口指向物理地址
		*pte = pa | PTE_P | perm;
		pa += PGSIZE;
		va += PGSIZE;
	}
}

//mpentry.S中的注释，解释了control flow transfer：
# Each non-boot CPU ("AP") is started up in response to a STARTUP

# IPI from the boot CPU.  Section B.4.2 of the Multi-Processor

# Specification says that the AP will start in real mode with CS:IP

# set to XY00:0000, where XY is an 8-bit value sent with the

# STARTUP. Thus this code must start at a 4096-byte boundary.

#

# Because this code sets DS to zero, it must run from an address in

# the low 2^16 bytes of physical memory.

#

# boot_aps() (in init.c) copies this code to MPENTRY_PADDR (which

# satisfies the above restrictions).  Then, for each AP, it stores the

# address of the pre-allocated per-core stack in mpentry_kstack, sends

# the STARTUP IPI, and waits for this code to acknowledge that it has

# started (which happens in mp_main in init.c).

//宏MPBOOTPHYS
#define MPBOOTPHYS(s) ((s) - mpentry_start + MPENTRY_PADDR)

# Start the CPU: switch to 32-bit protected mode, jump into C.

# The BIOS loads this code from the first sector of the hard disk into

# memory at physical address 0x7c00 and starts executing in real mode

# with %cs=0 %ip=7c00.

// kern/mpentry.S中的注释
# This code is similar to boot/boot.S except that

#    - it does not need to enable A20

#    - it uses MPBOOTPHYS to calculate absolute addresses of its

#      symbols, rather than relying on the linker to fill them

// kern/cpu.h
// Maximum number of CPUs
#define NCPU  8

// Values of status in struct Cpu
enum {
	CPU_UNUSED = 0,
	CPU_STARTED,
	CPU_HALTED,
};

// Per-CPU state
struct CpuInfo {
	uint8_t cpu_id;                 // Local APIC ID; index into cpus[] below
	volatile unsigned cpu_status;   // The status of the CPU
    // Per-CPU的当前环境指针
    // 每个CPU都能同步地执行不同的用户环境。
    // curenv=thiscpu->cpu_env，指向当前CPU(运行代码的CPU)上正在执行的环境。
	struct Env *cpu_env;            // The currently-running environment.
    
    // Per-CPU的TSS和TSS描述符
    // 每个CPU的任务状态段TSS同样需要指明其对应的内核栈位置
    // 每个CPU的TSS存放在CpuInfo中的cpu_ts域中，对应的描述符在GDT表项的gdt[(GD_TSS0 >> 3)+i]中
	struct Taskstate cpu_ts;        // Used by x86 to find stack for interrupt
};

// Initialized in mpconfig.c
extern struct CpuInfo cpus[NCPU];
extern int ncpu;                    // Total number of CPUs in the system
extern struct CpuInfo *bootcpu;     // The boot-strap processor (BSP)
extern physaddr_t lapicaddr;        // Physical MMIO address of the local APIC

// Per-CPU kernel stacks
// 多CPU可能同时陷入内核，所以需要为每个CPU设置独立的内核栈来避免相干扰
// percpu_kstacks[NCPU][KSTKSIZE]为NCPU个内核栈预留了空间
// CPU 0的内核栈从KSTACKTOP开始向下增长，之后第n个CPU的内核栈从KSTACKTOP - n*KSTKGAP处开始向下增长。如inc/memlayout.h中所示
extern unsigned char percpu_kstacks[NCPU][KSTKSIZE];

//cpunum()返回调用它的CPU ID，能用来做cpus[]数组的索引
int cpunum(void);

//宏thiscpu是当前CPU的struct CpuInfo的简写
#define thiscpu (&cpus[cpunum()])

	// Hints:
	//   - The macro "thiscpu" always refers to the current CPU's
	//     struct CpuInfo;
	//   - The ID of the current CPU is given by cpunum() or
	//     thiscpu->cpu_id;
	//   - Use "thiscpu->cpu_ts" as the TSS for the current CPU,
	//     rather than the global "ts" variable;
	//   - Use gdt[(GD_TSS0 >> 3) + i] for CPU i's TSS descriptor;
	//   - You mapped the per-CPU kernel stacks in mem_init_mp()
	//   - Initialize cpu_ts.ts_iomb to prevent unauthorized environments
	//     from doing IO (0 is not the correct value!)

// Initialize and load the per-CPU TSS and IDT
void trap_init_percpu(void)
{
	// The example code here sets up the Task State Segment (TSS) and
	// the TSS descriptor for CPU 0. But it is incorrect if we are
	// running on other CPUs because each CPU has its own kernel stack.
	// Fix the code so that it works for all CPUs.
	//
	// ltr sets a 'busy' flag in the TSS selector, so if you
	// accidentally load the same TSS on more than one CPU, you'll
	// get a triple fault.  If you set up an individual CPU's TSS
	// wrong, you may not get a fault until you try to return from
	// user space on that CPU.
	//
	// LAB 4: Your code here:
	int cid = thiscpu->cpu_id;
	// Setup a TSS so that we get the right stack
	// when we trap to the kernel.
    // esp0: 当前 CPU 的 stack 的起始位置
    // 根据cpu.h中可知：
    // CPU 0的内核栈从KSTACKTOP开始向下增长，之后第n个CPU的内核栈从KSTACKTOP - n*KSTKGAP处开始向下增长
	thiscpu->cpu_ts.ts_esp0 = KSTACKTOP - cid * (KSTKSIZE + KSTKGAP);
    // ts_ss0 = GD_KD 表示 esp0 这个位置存储的是kernel的data.ts_iomb: I/O map base address field
	thiscpu->cpu_ts.ts_ss0 = GD_KD;
    //设置I/O操作权限
	thiscpu->cpu_ts.ts_iomb = sizeof(struct Taskstate);

	// Initialize the TSS slot of the gdt.
    // 把TSS装载进GDT
	gdt[(GD_TSS0 >> 3) + cid] = SEG16(STS_T32A, (uint32_t)(&(thiscpu->cpu_ts)),
									  sizeof(struct Taskstate)-1, 0);
	gdt[(GD_TSS0 >> 3) + cid].sd_s = 0;

	// Load the TSS selector (like other segment selectors, the
	// bottom three bits are special; we leave them 0)
	ltr(GD_TSS0 + 8 * cid);

	// Load the IDT
	lidt(&idt_pd);
}

struct Segdesc gdt[] =
	{
		// 0x0 - unused (always faults -- for trapping NULL far pointers)
		SEG_NULL,
		// 0x8 - kernel code segment
		[GD_KT >> 3] = SEG(STA_X | STA_R, 0x0, 0xffffffff, 0),
		// 0x10 - kernel data segment
		[GD_KD >> 3] = SEG(STA_W, 0x0, 0xffffffff, 0),
		// 0x18 - user code segment
		[GD_UT >> 3] = SEG(STA_X | STA_R, 0x0, 0xffffffff, 3),
		// 0x20 - user data segment
		[GD_UD >> 3] = SEG(STA_W, 0x0, 0xffffffff, 3),
		// 0x28 - tss, initialized in trap_init_percpu()
		[GD_TSS0 >> 3] = SEG_NULL};

// spinlock.h
// Mutual exclusion lock.
struct spinlock {
	unsigned locked;       // Is the lock held?
};

static inline void
lock_kernel(void)
{
	spin_lock(&kernel_lock);
}

static inline void
unlock_kernel(void)
{
	spin_unlock(&kernel_lock);

	// Normally we wouldn't need to do this, but QEMU only runs
	// one CPU at a time and has a long time-slice.  Without the
	// pause, this CPU is likely to reacquire the lock before
	// another CPU has even been given a chance to acquire it.
	asm volatile("pause");
}

// Acquire the lock.
// Loops (spins) until the lock is acquired.
// Holding a lock for a long time may cause
// other CPUs to waste time spinning to acquire it.
void
spin_lock(struct spinlock *lk)
{
	// The xchg is atomic.
	// It also serializes, so that reads after acquire are not
	// reordered before it. 
	while (xchg(&lk->locked, 1) != 0)			//原理见：https://pdos.csail.mit.edu/6.828/2018/xv6/book-rev11.pdf  chapter 4
		asm volatile ("pause");	
}

// Release the lock.
void
spin_unlock(struct spinlock *lk)
{
	// The xchg instruction is atomic (i.e. uses the "lock" prefix) with
	// respect to any other instruction which references the same memory.
	// x86 CPUs will not reorder loads/stores across locked instructions
	// (vol 3, 8.2.2). Because xchg() is implemented using asm volatile,
	// gcc will not reorder C statements across the xchg.
	xchg(&lk->locked, 0);
}

// init.c
void
i386_init(void)
{
	//省略了其他内容……
	// Acquire the big kernel lock before waking up APs
	// Your code here:
    // 在BSP唤醒其它CPU之前，BSP获取内核锁，防止唤醒的AP启动进程
    // 这时启动的AP在等待锁的释放，阻塞在sched_yield()
	lock_kernel();	
	// Starting non-boot CPUs
	boot_aps();		
}

// init.c
// Setup code for APs
void
mp_main(void)
{
	// ……
	// Now that we have finished some basic setup, call sched_yield() to start running processes on this CPU.  
 	// But make sure that only one CPU can enter the scheduler at a time!
	// Your code here:
    // 初始化AP后，在调度之前上锁
    // 因为调用调度函数会进入内核临界区
	lock_kernel();
	sched_yield();
}

// trap.c
void trap(struct Trapframe *tf)
{
	// ……
	// Re-acqurie the big kernel lock if we were halted in sched_yield()
	if (xchg(&thiscpu->cpu_status, CPU_STARTED) == CPU_HALTED)
		lock_kernel();
	// Check that interrupts are disabled.  If this assertion
	// fails, DO NOT be tempted to fix it by inserting a "cli" in
	// the interrupt path.
	assert(!(read_eflags() & FL_IF));

	if ((tf->tf_cs & 3) == 3)
	{
		// Trapped from user mode.
		// Acquire the big kernel lock before doing any serious kernel work.
		// LAB 4: Your code here.
  		// 这里要从用户态进入到内核态
		assert(curenv);
		lock_kernel();

		// ……
}

// env.c
void
env_run(struct Env *e)
{
	if (curenv != NULL && curenv->env_status == ENV_RUNNING) {	
		curenv->env_status = ENV_RUNNABLE;
	}
	curenv = e;
	e->env_status = ENV_RUNNING;
	e->env_runs++;
	lcr3(PADDR(e->env_pgdir));
    // 释放锁
    // 因为在env_pop_tf执行结束之后回到用户态，所以要在env_pop_tf()之前释放
	unlock_kernel();						
	env_pop_tf(&e->env_tf);
}

// sched.c
// Choose a user environment to run and run it.
// 当env[i]进程来调用sched_yield()函数的时候，表示进程i要让出CPU了
void sched_yield(void)
{
	struct Env *idle;
	// Implement simple round-robin scheduling.
	//
	// Search through 'envs' for an ENV_RUNNABLE environment in circular fashion starting just after the env this CPU was last running.  Switch to the first such environment found.
	//
	// If no envs are runnable, but the environment previously running on this CPU is still ENV_RUNNING, it's okay to choose that environment.
	//
	// Never choose an environment that's currently running on another CPU (env_status == ENV_RUNNING). If there are no runnable environments, simply drop through to the code below to halt the cpu.
	// LAB 4: Your code here.

	int start = 0;
	int j;

    // 如果有curenv
	if (curenv)
	{
		start = ENVX(curenv->env_id) + 1; //start为当前进程的下一个进程（env_id）
	}
	for (int i = 0; i < NENV ; i++)
	{
		j = (start + i) % NENV; //循环遍历
		if (envs[j].env_status == ENV_RUNNABLE ) //找到就调用新进程
		{
			env_run(&envs[j]);
		}
	}
    // 如果没有找到ENV_RUNNABLE的进程，且当前进程还在跑，仍然执行当前进程
	if (curenv && curenv->env_status == ENV_RUNNING)
	{
		env_run(curenv);
	}
    // 当CPU没有环境可执行时，就会进入sched_halted()里被halted
	sched_halt();
}

void
env_run(struct Env *e)
{
	if (curenv != NULL && curenv->env_status == ENV_RUNNING) {	
		curenv->env_status = ENV_RUNNABLE;
	}
	curenv = e;
	e->env_status = ENV_RUNNING;
	e->env_runs++;
    // 题目说的是这里
	lcr3(PADDR(e->env_pgdir));
	unlock_kernel();						
	env_pop_tf(&e->env_tf);
}

static int env_setup_vm(struct Env *e)
{
	int i;
	struct PageInfo *p = NULL;

	// Allocate a page for the page directory
	if (!(p = page_alloc(ALLOC_ZERO)))
		return -E_NO_MEM;

	// Now, set e->env_pgdir and initialize the page directory.
	p->pp_ref++;
	e->env_pgdir = (pde_t *)page2kva(p);
    // env_pgdir基于kern_pgdir产生
	memcpy(e->env_pgdir, kern_pgdir, PGSIZE);

	// UVPT maps the env's own page table read-only.
	// Permissions: kernel R, user R
	e->env_pgdir[PDX(UVPT)] = PADDR(e->env_pgdir) | PTE_P | PTE_U;

	return 0;
}

// kern/env.c
void env_pop_tf(struct Trapframe *tf)
{
	// Record the CPU we are running on for user-space debugging
	curenv->env_cpunum = cpunum();

	asm volatile(
		"\tmovl %0,%%esp\n"
		"\tpopal\n"
		"\tpopl %%es\n"
		"\tpopl %%ds\n"
		"\taddl $0x8,%%esp\n" /* skip tf_trapno and tf_errcode */
		"\tiret\n"
		:
		: "g"(tf)
		: "memory");
	panic("iret failed"); /* mostly to placate the compiler */
}