BUAA-OS

「BUAA OS Lab2」名词解释

Posted by saltyfishyjk on 2022-04-20
Words 3.1k and Reading Time 13 Minutes
Viewed Times

「BUAA OS Lab2」名词解释

变量和类型

Pde和Pte

Page directory entry / Page table entry

声明：

1
2
typedef u_long Pde; 
typedef u_long Pte;

位置：include/mmu.h

Pde表示一个一级页表项，Pde表示一个二级页表项。二者本质为u_long。

PDX和PTX

Page Directory indeX / Page Table indeX

maxpa

maximum physical address

声明：

1
u_long maxpa;

位置：mm/pmap.c

最大物理地址+1，即$ [0,maxpa - 1] $范围内的所有整数所组成的集合等于物理地址的集合。

basemem

base memory

声明：

1
2
u_long basemem; 
basemem = maxpa;

位置：mm/pmap.c

物理内存对应的字节数

npage

number of pages

声明：

1
u_long npage;

位置：mm/pmap.c

总物理页数，npage个Page和npage个物理页面一一顺序对应，具体来说，npage个Page的起始地址为pages，则pages[i]对应从0开始计数的第i个物理页面，可以使用page2pa和pa2page相互转换。

extmem

extend memory

扩展内存的大小，在本实验中不涉及，置0。

end

声明：

1
2
. = 0x80400000;
end = .;
1
extend char end[];

位置：tools/scse0_3.lds（声明）mm/pmap.c（引用）

对应虚拟地址0x80400000，由映射规则知对应物理地址0x00400000，表明我们管理的物理空间 $ [0x00400000, maxpa - 1] $。又知道这段物理地址和虚拟地址 $ [0x80400000, 0x83fffff] $一一对应，因此虚拟地址被分配出去，代表对应的物理地址也被分配出去。

freemem

第一次调用mips_vm_init函数将其赋值为end即$ 0x80400000 $。其含义为 $ [0x80400000, freemem - 1 ]$的虚拟地址都已被分配。

LIST_ENTRY

位置：include/queue.h

1
2
3
4
5
#define LIST_ENTRY(type)                                                \
        struct {                                                                \
                struct type *le_next;   /* next element */                      \
                struct type **le_prev;  /* address of previous next element */  \
        }

本质上相当于一个工厂，生产一个type类型的链表结点结构体，其内容包含指向下一个结点的指针和指向上一个节点的下一个节点指针的指针。

举例来说，当我们调用typedef LIST_ENTRY(Page) Page_LIST_entry_t;时候，事实上为：

1
2
3
4
typedef struct {
	struct Page *le_next;
	struct Page **le_prev;
} Page_LIST_entry_t;

即，构造了一个类型名为Page_LIST_entry_t，作为Page结构体的链表项。

Page

位置：include/pmap.h

1
2
3
4
5
6
7
8
9
10
struct Page {
	Page_LIST_entry_t pp_link;	/* free list link */

	// Ref is the count of pointers (usually in page table entries)
	// to this page.  This only holds for pages allocated using 
	// page_alloc.  Pages allocated at boot time using pmap.c's "alloc"
	// do not have valid reference count fields.

	u_short pp_ref;
};

Page Directory与Page Table

第一级表称为页目录（Page Directory），第二级表称为页表（Page Table）。

PFN

Physical Frame Number

物理页框号

PPN

Physical Page Number

1
#define PPN(va)		(((u_long)(va))>>12)

VPN

Virtual Page Number

LEAF

在汇编代码中定义不包含对其他函数调用的函数。

NESTED

在汇编代码中定义需要调用其他函数的函数。

END

在汇编代码中结束对函数的定义。

定义在struct Page中的变量，意为page pointer link，是Page的链表项。

pp_ref

定义在struct Page中的变量，意为page pointer refference，等于有多少虚拟页映射到该物理页。

PTE_V

valid

PTE_R

writable

BY2PG

BYtes to a PaGe

1
#define BY2PG 4096

ULIM

User limit

1
#define ULIM 0x80000000

小于ULIM的虚拟地址位于kuseg，紧挨着kuseg的是kseg0

PDMAP

Page Directory Map, bytes mapped by a page directory entry

1
#define PDMAP (4 * 1024 * 1024) // bytes mapped by a page directory entry

UVPT

User VPT 

1
#define UVPT (ULIM - PDMAP)

UVPT = 0x7fc0,0000

UPAGES

User Pages

1
#define UPAGES (UVPT - PDMAP)

UPAGES = 0x7f80,0000

UENVS

User ENVS

1
#define UENVS (UPAGES - PDMAP)

UENVNS = 0x7f40,0000

函数和宏函数

mips_detect_memory()

返回值：void

位置：mm/pmap.c

对一些和内存管理相关的变量进行初始化，包括maxpa,basemem,npage,extmem。

mips_vm_init

返回值：void

位置：mm/pmap.c

mips virtual memory init

alloc(u_int n, u_int align, int clear)

返回值：static void *

位置：mm/pmap.c

分配n字节空间并返回初始虚拟地址；同时保证align（中文意思为’对齐’）可以整除初始虚拟地址；若clear为真则将对应空间的值清零，否则不清零。

LIST_HEAD(name, type)

位置：include/queue.h

创建一个名称为name链表的头部结构体，包含一个指向type类型结构体的指针，指针可以指向链表的首个元素。在我们的实验中，pmap.h中调用了LIST_HEAD(Page_list, Page);。

1
2
3
4
#define LIST_HEAD(name, type)                                           \
        struct name {                                                           \
                struct type *lh_first;  /* first element */                     \
        }

当调用LIST_HEAD(Page_list, Page);，实际上相当于：

1
2
3
struct Page_list {
    struct Page *lh_first;
}

LIST_ENTRY(type)

位置：include/queue.h

LIST_EMPTY(head)

位置：include/queue.h

1
#define LIST_EMPTY(head)        ((head)->lh_first == NULL

判断头部结构体是否为空。

LIST_FIRST(head)

位置：include/queue.h

返回头部结构体head对应的链表的首个元素。

1
#define LIST_FIRST(head)        ((head)->lh_first)

LIST_INIT(head)

位置：include/queue.h

将头部结构体head对应的链表初始化，等价于将首个元素清空。

1
2
3
#define LIST_INIT(head) do {                                            \
                LIST_FIRST((head)) = NULL;                                      \
        } while (0)

LIST_NEXT(elm, field)

位置：include/queue.h

结构体elm包含的名为field的数据，类型是一个链表项LIST_ENTRY(type)，返回其指向的下一个元素。

1
#define LIST_NEXT(elm, field)   ((elm)->field.le_next)

LIST_INSERT_AFTER(listelm, elm, field)

位置：queue.h

LIST_INSERT_HEAD(head, elm, field)

位置：queue.h

page_decref(struct Page *pp)

page_free

PDX(va)

位置：include/mmu.h

1
#define PDX(va) ((((u_long)(va)) >> 22) & 0x03FF)

Page Directory Index，一级页表号，或一级页表项偏移量（指针加法即可）

获取虚拟地址va的 $ 31 - 22 $ 位

PTX(va)

位置：include/mmu.h

1
#define PTX(va) ((((u_long)(va)) >> 12) & 0x03FF)

Page Table Index，二级页表号，或二级页表项偏移量（指针加法即可）

获取虚拟地址va的 $ 21 - 12 $ 位

PADDR(va)

Physical Address

返回虚拟地址va对应的物理地址。要求vaixu是kseg0的虚拟地址，因此只需要将最高位清零就可以得到对应的物理地址。

KADDR(pa)

Kernal Address(virtual)

返回物理地址pa对应的kseg0的虚拟地址

1
2
3
4
5
6
7
8
#define KADDR(pa)                                                        \
	(                                                                    \
		{                                                                \
			u_long ppn = PPN(pa);                                        \
			if (ppn >= npage)                                            \
				panic("KADDR called with invalid pa %08lx", (u_long)pa); \
			(pa) + ULIM;                                                 \
		})

PTE_ADDR(pte)

Page Table Entry Address

PTE（和TLB中的EntryLo结构相同）结构如上图示

1
#define PTE_ADDR(pte) ((u_long)(pte) & ~0xFFF)

对于给定的pte项，将低12位清零，得到页框号（即页号）PFN(Page Frame Number)左移12位的结果即物理地址。

bzero

位置：init/init.c

将每一个字节清空。

bcopy

位置：init/init.c

从src拷贝len个字节到dst

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void bcopy(const void *src, void *dst, size_t len)
{
	void *max;

	max = dst + len;
	// copy machine words while possible
	while (dst + 3 < max)
	{
		*(int *)dst = *(int *)src;
		dst += 4;
		src += 4;
	}
	// finish remaining 0-3 bytes
	while (dst < max)
	{
		*(char *)dst = *(char *)src;
		dst += 1;
		src += 1;
	}
}

boot_pgdir_walk

二级页表检索函数

返回值：Pte*，返回指向检索到的二级页表页表项的指针。

返回一级页表基地址pgdir对应的两级页表结构中，va虚拟地址所在的二级页表项。

这一函数在内核启动过程中被调用。

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
static Pte *boot_pgdir_walk(Pde *pgdir, u_long va, int create)
{

	Pde *pgdir_entryp;
	Pte *pgtable, *pgtable_entry;

	/* Step 1: Get the corresponding page directory entry and page table. */
	/* Hint: Use KADDR and PTE_ADDR to get the page table from page directory
	 * entry value. */
	pgdir_entryp = pgdir + PDX(va);

	/* Step 2: If the corresponding page table is not exist and parameter `create`
	 * is set, create one. And set the correct permission bits for this new page
	 * table. */
	if (!((*pgdir_entryp) & PTE_V)) { 
		if (create) {
            // 当页表项不存在且create=1时，为该二级页表项申请一个页，将二级页表项指向这个新的页，并设置权限表明该二级页表项可用
            // 实际上，最开始的二级页表项几乎都是空的不可用的，这里逐渐使得二级页表项可用。
			*pgdir_entryp = PADDR(alloc(BY2PG, BY2PG, 1));
			*pgdir_entryp = (*pgdir_entryp) | PTE_V | PTE_R;
		} else {
			return 0;
		}
	}
	pgtable = (Pte *) KADDR(PTE_ADDR(*pgdir_entryp));

	/* Step 3: Get the page table entry for `va`, and return it. */
	pgtable_entry = pgtable + PTX(va);
	return pgtable_entry;	
}

boot_map_segment

返回值：void boot_map_segment(Pde *pgdir, u_long va, u_long size, u_long pa, int perm)

区间地址映射函数。将一级页表基地址pgdir对应的两级页表结构做区间地址映射，将虚拟地址空间 $ [va, va + size - 1] $ 映射到物理地址区间 $ [pa, pa + size - 1] $ 。由于按页映射，要求size是页面大小的整数倍。设置页表项的权限位为perm。函数调用了boot_pgdir_walk，为Page结构体和Env结构体进行映射。

这一函数在内核启动过程中被调用。

pgdir_walk

boot_pgdir_walk的非启动版本，允许失败。

int pgdir_walk(Pde *pgdir, u_long va, int create, Pte **ppte)

返回值：int，为0则执行成功，否则返回一个失败码

page_insert

增加地址映射函数，将一级页表基地址pgdir对应的两级页表结构中va这一虚拟地址映射到内存控制块pp对应的物理页面，并将页表项权限位设置为perm。

int page_insert(Pde *pgddir, struct Page *pp, u_long va, u_int perm)

返回值：int，成功执行时返回0，否则返回-E_NO_MEM

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
int page_insert(Pde *pgdir, struct Page *pp, u_long va, u_int perm)
{
	u_int PERM;
	Pte *pgtable_entry;
	PERM = perm | PTE_V;

	/* Step 1: Get corresponding page table entry. */
	pgdir_walk(pgdir, va, 0, &pgtable_entry);

	if (pgtable_entry != 0 && (*pgtable_entry & PTE_V) != 0) {
		if (pa2page(*pgtable_entry) != pp) {
			page_remove(pgdir, va);
		} else	{
			tlb_invalidate(pgdir, va);
			*pgtable_entry = (page2pa(pp) | PERM);
			return 0;
		}
	}

	/* Step 2: Update TLB. */

	/* hint: use tlb_invalidate function */
	tlb_invalidate(pgdir, va);

	/* Step 3: Do check, re-get page table entry to validate the insertion. */

	/* Step 3.1 Check if the page can be insert, if can’t return -E_NO_MEM */
	if (pgdir_walk(pgdir, va, 1, &pgtable_entry) != 0) {
		return -E_NO_MEM;
	}
	/* Step 3.2 Insert page and increment the pp_ref */
	*pgtable_entry = page2pa(pp) | PERM;
	pp->pp_ref++;	
	return 0;
}

page_lookup

struct Page *page_lookup(Pde *pgdir, u_long va, Pte **ppte)

返回值：struct Page *

返回一级页表及地址pgdir对应的两级页表结构中va这一虚拟地址映射对应的物理页面对应的内存控制块，并且将va的二级页表项存到ppte中。

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
struct Page *
page_lookup(Pde *pgdir, u_long va, Pte **ppte) {
    struct Page *ppage;
    Pte *pte;

    /* Step 1: Get the page table entry. */
    pgdir_walk(pgdir, va, 0, &pte);

    /* Hint: Check if the page table entry doesn't exist or is not valid. */
    if (pte == 0) {
        return 0;
    }
    if ((*pte & PTE_V) == 0) {
        return 0;    //the page is not in memory.
    }

    /* Step 2: Get the corresponding Page struct. */

    /* Hint: Use function `pa2page`, defined in include/pmap.h . */
    ppage = pa2page(*pte);
    if (ppte) {
        *ppte = pte;
    }

    return ppage;
}

page_remove

void page_remove(Pde *pgdir, u_long va)

取消地址映射函数

删除一级页表基地址pgdir对应的两级页表结构中va这一虚拟地址对应物理地址的映射。如果存在这样的映射，那么对应物理页面结构的引用次数会减少。

pageout

void pageout(int va, int context)

被动地址映射函数

一级页表基地址context对应的两级页表结构中va新增这一虚拟地址的映射，对应的物理页面通过函数page_alloc获取而不特殊指定。

tlb_invalidate

void tlb_invalidate(Pde *pgdir, u_long va)

实现删除特定虚拟地址的映射。

当页表被修改时，需要调用该函数保证下次访问该虚拟地址时会诱发TLB重填以保证访存的正确性。

page2ppn

1
2
3
4
page2ppn(struct Page *pp)
{
	return pp - pages;
}

利用Page和pages（Page ）确定offset，类似Page数组的下标

page2pa

1
2
3
4
static inline u_long page2pa(struct Page *pp)
{
	return page2ppn(pp)<<PGSHIFT;
}

获得pp（大概为Page pointer）“下标”，左移页大小可得物理地址pa（physical address)。

pa2page

1
2
3
4
5
6
pa2page(u_long pa)
{
	if (PPN(pa) >= npage)
		panic("pa2page called with invalid pa: %x", pa);
	return &pages[PPN(pa)];
}

根据pa（physical address），

page_init

  • 使用链表初始化宏对page_free_list初始化。

  • 将freemem圆整

  • 将freemem以下的页面标记为pp_ref =表示已经使用过
  • 将freemem以上的页面的pp_ref清零并插入page_free_list中表示为可用物理页面

page_alloc

返回值：int，返回值不为0表明出现异常

page_alloc(struct Page **pp)

将page_free_list空闲链表头部内存控制块对应的物理页面分配出去，将其从空闲链表中移除，并清空对应的物理页面，最后将pp指向的空间赋值为这个内存控制块的地址。

在这之中，我们使用了LIST_EMPTY判断空闲链表中是否还有页面；使用了LIST_FIRST取出了page_free_list对应的第一个页面；使用了LIST_REMOVE()将这个页面从page_free_list中移除；使用bzero将页面初始化。

page2kva

1
2
3
4
page2kva(struct Page *pp)
{
  return KADDR(page2pa(pp));
}

page_decref

page_decref(struct Page *pp)

1
2
3
4
5
void page_decref(struct Page *pp) {
	if(--pp->pp_ref == 0) {
		page_free(pp);
	}
}

令pp对应内存控制块的引用次数减少1。如果引用次数为0，会接着调用page_free将对应的物理页面重新设置为空闲页面

page_free

page_free(struct Page *pp)

判断pp指向内存控制块对应的物理页面引用次数是否为0，如果是的话该物理页面为空闲页面，将其重新插入到page_free_list

ROUND

1
#define ROUND(a, n)	(((((u_long)(a))+(n)-1)) & ~((n)-1))

圆整，返回 $ \lceil\frac{a}{n} \rceil n $ ，要求 $ n $ 必须是 $ 2 $ 的非负整数次幂。

效果是将 $ a $ 向上圆整为 $ n $ 的整数倍。

ROUNDDOWN

1
#define ROUNDDOWN(a, n)	(((u_long)(a)) & ~((n)-1))

圆整，返回 $ \lfloor \frac{a}{n} \rfloor n $ ，要求 $ n $ 是 $ 2 $ 的非负整数次幂。

效果是将 $ a $ 向下圆整为 $ n $ 的整数倍。

This is copyright.

FEATURED TAGS
BUAA-OS
FRIENDS