[MIT6.828]LAB2 Challenge 总结

Challenge 1: 大页机制的实现
没有在代码中实现，写了个步骤供参考：
0、先把预定义的PGSIZE之类的宏都更改为与大页相匹配的情况。
1、由于页大小变成了4M，所以要修改从代码，要内核4M处加载。
3、page_init()中内存布局也会发生对应变化，低端4M保留给实模式和IO映射，然后4M-8M是内核代码数据，8M-16M可以用来放置页目录以及物理页面数据结构，其他空闲。
4、用于页面映射的操作的pgdir_walk(),page_insert(),page_remove(),page_lookup(),boot_map_segment()这些函数要修改，首先是物理寻址只需要页目录一层就足够了，其次要给页属性加上PTE_PS标志位用来表示大页。
5、映射物理内存到线性内存的时候需要注意这时候内核栈没有页对齐，而是在内核代码数据这个大页里面，内核栈也可以不用映射，用bootstacktop变量代替。但是数据溢出后会覆盖内核代码及其以前的区域，不能保证安全性（原内核栈数据溢出后会挂死，因为访问了未映射的页）。如果想要使用跟原内核一样的行为，必须修改内核代码，把栈和代码分开，例如放到内核开头的，这时候第3步的内存布局发生变化。在映射完毕的时候也需要注意为了防止溢出影响到别的数据，要用一页的虚拟内存映射为空放到内核栈的下面。

Challenge 2:添加showmappings dump等查看内存/页 的命令
在monitor.c文件中实现了如下命令：
1、showmapping(别名sm）：用来显示页面映射状态（monitor.c/show_mapping() pmap.h/pagepri2str()）

//kern/monitor.c
#define TESTERR(a)	{if(a)	goto ERR;}
#define LERR		ERR:{cprintf("Wrong parameters!\n");return 0;}

//kern/pmap.h
static inline char *
pagepri2str(pte_t pte, char *buf)
{
	int i;
	static const char *str[]={"_________SR_","AVLGPDACTUWP"};
	for(i=0; i<12; ++i)
	{
		buf[i] = str[(pte>>(11-i))&0x1][i];
	}
	buf[i] = '\0';
	return buf;
}

int
show_mapping(int argc, char **argv, struct Trapframe *tf)
{
	uint32_t begin ,end;
	char *endptrb, *endptre;
	if (argc == 2)//sm addr
	{	
		begin = ROUNDDOWN((uint32_t)strtol(argv[1], &endptrb, 0),PGSIZE);
		end = begin + PGSIZE;
		TESTERR ( *endptrb != '\0');
	}
	else if (argc == 3)//sm beginaddr endaddr 
	{
		begin = ROUNDDOWN((uint32_t)strtol(argv[1], &endptrb, 0),PGSIZE);
		end = ROUNDUP((uint32_t)strtol(argv[2], &endptre, 0),PGSIZE);
		TESTERR ( *endptrb != '\0' || *endptre != '\0');
	}
	else
	{	
		goto ERR;
	}
	cprintf("\tVirtual\t\tPhysical\tPriority\tRefer\n");
	for (; begin!=end; begin += PGSIZE)
	{
		struct Page *pp;
		pte_t *ppte;
		char buf[13];
		pp = page_lookup(PGADDR(PDX(VPT),PDX(VPT),0), (void *)begin, &ppte);
		if (pp == NULL || *ppte ==0)
			cprintf("\t%08x\t%s\t%s\t\t%d\n", begin, "Not mapping", "None", 0);
		else
			cprintf("\t%08x\t%08x\t%s\t%d\n", begin, page2pa(pp),pagepri2str(*ppte, buf), pp->pp_ref );
	}
	
	return 0;	 
ERR:
	cprintf("Wrong parameters!\n");
	return 0; 
}

2、spp：设置页面属性(monitor.c/set_pagepriority() pmap.h/str2pagepri())

//kern/pmap.h
static inline int
str2pagepri(const char *buf)
{
	int pri = 0;
	while (*buf != '\0')
	{
		switch (*buf++)
		{
			case 'p':
			case 'P':	STPTE_P(pri);	break;
			case 'w':
			case 'W':	STPTE_W(pri);	break;
			case 'u':
			case 'U':	STPTE_U(pri);	break;
			case 't':
			case 'T':	STPTE_PWT(pri);	break;
			case 'c':
			case 'C':	STPTE_PCD(pri);	break;
			case 'a':
			case 'A':	STPTE_A(pri);	break;
			case 'd':
			case 'D':	STPTE_D(pri);	break;
			/*case 'p':
			case 'P':	STPTE_PS(pri);	break;
			*/
			default:	break;
		}
	}
	return pri;
}

int
set_pagepriority(int argc, char **argv, struct Trapframe *tf)
{
	uint32_t pte ;
	uint32_t begin;
	pte_t * ppte;
	struct Page *pp;
	char *endptr;
	char buf_old[13],buf_new[13];
	if (argc != 3 && argc != 4)
		goto ERR;
	begin = ROUNDDOWN((uint32_t)strtol(argv[1], &endptr, 0),PGSIZE);
	TESTERR (*endptr != '\0');
	pp = page_lookup(PGADDR(PDX(VPT),PDX(VPT),0), (void *)begin, &ppte);
	
	if (pp == NULL || *ppte == 0)
	{	
		cprintf("\tVirtual\t\tPhysical\tOld Priority\tNew Priority\tRefer\n");
		cprintf("\t%08x\t%s\t%s\t\t%s\t\t%d\n",begin, "No Mapping", "None", "None", 0);
		return 0;
	}
	pte = *ppte;
	
	if (argc == 3)
	{
		if(*argv[2] == '+')//spp pageaddr +pri
		{
			*ppte |=str2pagepri(argv[2]+1);	
		}
		else if (*argv[2] == '-')//spp pageaddr -pri
		{
			*ppte &= ~str2pagepri(argv[2]+1);
		}
		else//spp pageaddr pri
		{
			*ppte = PTE_ADDR(*ppte)|strtol(argv[2], &endptr, 0);
			TESTERR ( *endptr != '\0');
		}
	}
	else
	{
		if( *argv[2] == '+') //spp pageaddr +pri1 -pri2
		{
			if ( *argv[3] == '-')
			{
				*ppte = (*ppte|str2pagepri(argv[2]+1))& (~str2pagepri(argv[3]+1));
			}
		}
	}
	
TODO:
	if (ISPTE_P(pte) != ISPTE_P(*ppte))
	{
		if (ISPTE_P(pte))
			pp->pp_ref --;
		else
			pp->pp_ref ++;
	}
	
	cprintf("\tVirtual\t\tPhysical\tOld Priority\tNew Priority\tRefer\n");
	cprintf("\t%08x\t%08x\t%s\t%s\t%d\n", begin,  page2pa(pp),  pagepri2str(pte,buf_old), pagepri2str(*ppte, buf_new), pp->pp_ref);
	return 0;
ERR:
	cprintf("Wrong parameters!\n");
	return 0;
}

3、dump：查看内存的内容(dump()函数)

int dump(int argc, char **argv, struct Trapframe *tf)
{
	int flag = 0;
	uint32_t begin,end;
	char *endptrb, *endptre;
	TESTERR (argc !=2 && argc != 3 && argc !=4);
	if (argc == 2) // dump addr (Virtual Address)
	{
		begin = strtol(argv[1], &endptrb, 0);
		end = begin + 16;
		TESTERR(*endptrb != '\0');
	}
	else if (argc == 3)
	{
		if (*argv[1]== '-')
		{
			if (argv[1][1] == 'p') //dump -p addr (Physical Address)
				flag = 1;
			else TESTERR (argv[1][1] != 'v');//dump -v addr (Virtual Address)
			begin = strtol(argv[2], &endptrb, 0); 
			end = begin +16;
			TESTERR(*endptrb!='\0');
		}
		else
		{	//dump xxxx xxxx
			begin = strtol(argv[1], &endptrb, 0);
			end = strtol(argv[2], &endptre, 0);
			TESTERR (*endptrb != '\0' || *endptre != '\0');
		}
	}
	else
	{
		if (strcmp(argv[1],"-p") == 0) //dump -p beginaddr endaddr (Physical Address)
			flag =1;
		else TESTERR (strcmp(argv[1], "-v") !=0 ); //dump -v beginaddr endaddr (Virtual Address)
		begin = strtol(argv[2], &endptrb, 0);
		end = strtol(argv[3], &endptre, 0);
		TESTERR (*endptrb != '\0' || *endptre != '\0');
	}
	if (flag)
	{	//process physical memory
		if (begin > maxpa || end > maxpa)
		{
			cprintf("Over than max physical memory\n");
			return 0;
		}
		begin = (uint32_t)KADDR(begin);
		end = (uint32_t)KADDR(end);
	}
	
	while (begin <end)
	{
		int i;
		pte_t *ppte;
		cprintf("%08x ",begin);
		if (page_lookup(PGADDR(PDX(VPT),PDX(VPT),0), (void *)begin, &ppte) == NULL 
			|| *ppte == 0)
		{
			cprintf("No Mapping\n");
			begin += PGSIZE - begin%PGSIZE;
			continue;
		}
		cprintf("%08x\t", PTE_ADDR(*ppte)|PGOFF(begin));
		for (i=0; i < 16 ; i++, begin ++)
		{
			cprintf("%02x ",*(unsigned char *)begin);
		}
		cprintf("\n");
	}
	return 0;
ERR:
	cprintf("Wrong parameters!\n");
	return 0;
}

具体内容见附件，命令使用方法见help命令

Challenge 3: 用户态4G虚拟地址可用的设计方案
1、权限转化方式
只使用调用门来从用户态转向内核态。
2、内核映射方式
首先寻找未被使用的虚拟地址，如果找不到，则兑换出一块内存到硬盘，把兑换信息记录到内核中，把该块地址映射到内核，标志为kenel权限，并更改调用门中或者其他hardcoding的内核地址（为了这里修改方便，内核重要虚拟地址尽量不要写死，可以用宏的方式来实现）。跳转的新映射的内核地址，然后根据已保存信息将旧页恢复（标记为空闲或者把曾经兑换到硬盘的页读入进来）。
3、异常处理机制
用户程序访问到被内核占用的页面，会产生保护错误。在保护错误处理过程中，根据保护错误类型（这里是U/S权限出错）执行2操作。
4、优点：应用程序可以占用全部虚拟空间，提高了应用程序设计的灵活性，以及对需要超大内存空间程序的支持。
5、缺点：增加了内核的复杂度，降低了性能，尤其处理U/S权限保护错误的时候需要做很多操作。
6、总结：32位程序还够用的时候，64位已经大行其道；受限于机器性能，一台机器上同时运行的程序不会非常多，以及绝大多数程序不需要超大虚拟内存；以及上述的缺点使得这种行为意义不大。

Challenge 4: 给内核添加连续物理页分配功能

修改了struct Page结构，使其可以保存连续物理页分配状态，声明了一个page_alloc_list 队列保存已分配物理页，并在init_page()函数里初始化。

//inc/memlayout.h
struct Page {
	Page_LIST_entry_t pp_link;	/* free list link */
	uint16_t pp_ref;
	uint16_t pp_cnt;//add by dave
};

在pmap.c中添加了如下函数
1、void *kalloc();分配一个页并返回其内核虚拟地址

void *
kalloc()
{
	struct Page *pp;
	if (page_alloc(&pp) == -E_NO_MEM)
		return NULL;	
	pp->pp_cnt = pp->pp_ref = 1;
	LIST_INSERT_HEAD(&page_alloc_list, pp, pp_link);
	return page2kva(pp);
}

2、void *kallocs(size_t size);分配大小为size且在物理内存中连续的页；

void *
kallocs(size_t size)
{
	size = ROUNDUP(size, PGSIZE)>>PGSHIFT;
	int i ,j;
	for (i=j=0; i<npage; i++)
	{
		if(pages[i].pp_ref == 0)
		{
			if (++j == size)
				break;
		}
		else
			j = 0;
	}
	if (j != size)
		return NULL;
	for(j= i-size; i>j; i--)
	{
		LIST_REMOVE(pages+i, pp_link);
		page_initpp(pages+i);
		pages[i].pp_ref = 1;
	}
	pages[++i].pp_cnt = size;
	LIST_INSERT_HEAD(&page_alloc_list, pages+i, pp_link);
	return page2kva(pages+i);
}

3、void kfree(void *ptr);释放内存

void kfree(void *ptr)
{
	struct Page *pp = kva2page(ptr);
	LIST_REMOVE(pp, pp_link);
	for(;pp->pp_cnt>0; pp->pp_cnt-- )
	{
		pp[pp->pp_cnt-1].pp_ref = 0;
		page_free(pp+pp->pp_cnt-1);
	}
}

4、void kffree(void *ptr);强制释放处于连续分配页中的内存页（从当前地址释放到连续分配的末尾）

void kffree(void *ptr)
{
	physaddr_t hpa, pa = PADDR(PTE_ADDR(ptr));
	int count , seq;
	if (kpage_status(pa, &hpa, &count) <=0)
		return ;
	if (pa != hpa)
	{
		seq = (pa -hpa)>>PGSHIFT;
		pages[PPN(hpa)].pp_cnt = seq;
		pages[PPN(pa)].pp_cnt = count -seq;
		LIST_INSERT_HEAD(&page_alloc_list, pa2page(pa), pp_link);
	}
	kfree(ptr);
}

5、int kpage_status(physaddr_t pa, physaddr_t *head_pa, int *cnt); 查询位于pa处物理页面的信息

int kpage_status(physaddr_t pa, physaddr_t *head_pa, int *count)
{
	if (head_pa== NULL || count == NULL )
		return -1;
	int pn = PPN(pa);
	if (pn > npage)
		return -1;
	if (pages[pn].pp_ref == 0)
		return 0;
	if(pages[pn].pp_cnt !=0)
	{
		*head_pa = PTE_ADDR(pa);
		*count = pages[pn].pp_cnt;
	}
	else
	{	//searh head;
		int i;
		for (i=2,pn--; pn>0; pn--,i++)
		{
			if (pages[pn].pp_cnt !=0 )
			{	
				*head_pa = page2pa(pages+pn);
				*count	= pages[pn].pp_cnt;
				break;
			}
		}
	}
	return 1;
}

Challenge 5: 添加分配/查看/释放页的命令
在monitor.c中实现了如下命令
1、allocpage: 分配一个或者多个页(alloc_pages()函数)

int alloc_pages(int argc, char **argv, struct Trapframe *tf)
{
	int n = 1 , i = 1;
	void *ptr;
	char *endptr;
	TESTERR (argc  != 1 && argc != 2 && argc !=3);
	if (argc != 1)
	{
		if (argc == 3)
		{	//allocpage -s xxxx	
			i = 2;
			TESTERR(strcmp(argv[1], "-s")!=0);
		}
		n = strtol(argv[i], &endptr, 0);
		TESTERR(*endptr != '\0');
	}
	if (i == 2) 
	{	// alloc physical sequence pages
		if ((ptr = kallocs(n<<PGSHIFT)) == NULL)
		{
			cprintf("No enough memory\n");
		}
		else
		{
			cprintf("Allocated:\n");
			for(i=0; i<n; i++)
			{
				cprintf("\t%08x",PADDR(ptr)+(i<<PGSHIFT));
			}
			cprintf("\n");
		}
	}
	else
	{	//alloc any pages
		cprintf ("Allocated:\n");
		for (i=0 ;i<n; i++)
		{
			if ( (ptr=kalloc()) ==NULL)
			{
				cprintf("\nNo enough memory\n");
				break;
			}
			else
				cprintf("\t%08x",PADDR(ptr));
		}
		 cprintf("\n");		
	}
	
	return 0;
ERR:
	cprintf("Wrong parameters!\n");
	return 0;
}

2、freepage: 释放一个或者多个页(free_pages()函数)

int free_pages(int argc, char **argv, struct Trapframe *tf)
{
	TESTERR(argc !=2 && argc !=3);
	int ret ,cnt, i=1 ,force = 0;
	physaddr_t pa,hpa;
	char *endptr;
	if (argc == 3)
	{
		TESTERR(strcmp(argv[1], "-f") !=0 ); //freepage -f pageaddr
		argv[1] = argv[2];
		i = 2;
		force = 1;
	}
	pa = strtol(argv[i], &endptr, 0);
	TESTERR( *endptr != '\0');
	ret = page_status(2, argv, tf);
	if (ret != 2)
		return 0;
	kpage_status(pa, &hpa, &cnt);
	if( PTE_ADDR(pa) == hpa )
		kfree(KADDR(hpa));
	else
	{
		if (force)
		{
			kffree(KADDR(pa));		
		}
		else
		{
			cprintf("Must free from head page, or use -f option!\n");
			return 0;
		}
	}
	page_status(2, argv, tf);
	return 0;
	LERR;
}

3、pagestatus: 查看指定页面状态(page_status()函数)

int page_status(int argc, char **argv, struct Trapframe *tf)
{
	TESTERR(argc != 2);
	char *endptr;
	int ret ,cnt;
	physaddr_t hpa, pa = strtol(argv[1], &endptr, 0);
	TESTERR(*endptr != '\0');
	if (PPN(pa)> npage)
	{
		cprintf ("More than physical memory!\n");
		return 0;
	}
	ret = kpage_status(pa, &hpa, &cnt);
	if (ret < 0)
	{	
		cprintf("Check status error!\n");
		return 0;
	}
	else if(ret == 0)
	{
		cprintf("Page %08x free\n" ,PTE_ADDR(pa));
		return 1;
	}
	else
	{
		cprintf("Page %08x allocated, head page: %08x, count: %d, sequnce: %d .\n",PTE_ADDR(pa), hpa, cnt, (pa-hpa)>>PGSHIFT);
		return 2;
	}
	return 0;
	LERR;
	
}

修改了mon_help()，和struct command结构体，使得帮助信息更完善。其他地方也做了一些小修改，使得UI更为友好，但是还有很多不足之处没有时间一一完善，其实一个人用的话没必要这么做个详细（尤其是帮助），主要是想和大家多多交流。

struct Command {
	const char *name;
	const char *desc;
	const char *usage;
	// return -1 to force monitor to exit
	int (*func)(int argc, char** argv, struct Trapframe* tf);
};
int
mon_help(int argc, char **argv, struct Trapframe *tf)
{
	int i;
	
	if (argc == 2)
	{
		for (i = 0; i< NCOMMANDS; i++)
		{
			if (strcmp(argv[1], commands[i].name) == 0)
				break;
		}
		if (i >= NCOMMANDS)
			cprintf("Command \"%s\" hasn't been implemented\n", argv[1]);
		else
		{
			cprintf ("%s\n\nUsage: %s\n",commands[i].desc, commands[i].usage);
		}
	}
	else{
		for (i = 0; i < NCOMMANDS; i++)
			cprintf("%s - %s\n", commands[i].name, commands[i].desc);
		cprintf("\n%s\n",commands[0].usage);
	}
	return 0;
}

EOF