Minix内存管理
1概述
Minix 在设计时被分成了四层，如下图所示，第1层和第2层是进程管理和I/O任务，合称为Minix的核心(kernel), 内存管理(Memory Manager,下文简称MM) 并不是内核的一部分，它位于内核之上的第三层，主要处理的是FORK,EXEC,BRK等涉及到内存访问的系统调用。它和内核之间通过消息来通信。
本文首先介绍内存管理最基本的部分：物理内存的分配和回收，然后介绍和内存分配相关的系统调用，例如FORK、EXEC、
BRK、信号处理等，其中会涉及到进程管理和文件系统。通过本文的介绍，大家会对Minix的内存管理有大致的了解，并且能够清楚的看到一段可执行代码如何被装入内存，分配资源后执行的。
注：下文中程序的行号和《操作系统：设计与实现》一书中附录A保持一致
2物理内存的分配和回收
内存管理的策略有很多，比如交换、分页、分段、段页式等，Minix的内存管理非常简单：既不分页也不交换。存储管理器保存着一张按照内存地址排列的空洞列表。当由于执行系统调用FORK或EXEC需要内存时，系统特用首次适配算法对空洞列表进行按索找出一个足够大的空洞。一旦一个程序被装入内存，它将一直保持在原来的位置直到运行结束，它永远不会被换出或移动到内存的其他位置去，为它分配的空间也不会增长或缩小。
物理内存管理主要包括下面几种功能：
1. 内存初始化：当MM启动时需要初始化内存空洞表
2. 分配指定大小的内存
3. 释放一块以前分配的内存
4. 返回当前最大空洞的大小
空洞列表的数据结构如下：
18820 #define NR_HOLES 128 /* max # entries in hole table */
18821 #define NIL_HOLE (struct hole *) 0
18822
18823 PRIVATE struct hole {
18824 phys_clicks h_base; /* 空洞的开始地址*/
18825 phys_clicks h_len; /* 空洞的长度 */
18826 struct hole *h_next; /* 指向下一个空洞 */
18827 } hole[NR_HOLES];
18830 PRIVATE struct hole *hole_head; /* pointer to first hole */
18831 PRIVATE struct hole *free_slots; /* ptr to list of unused table slots */
上面的数据结构说明，空洞表中共有128个表项，各个表项之间通过指针连接成一个链表。
指针hole_head指向第一个空洞，free_slots的含义在下文会说明
由于MM采用了非常简单的策略,所以其数据结构也非常简单，操作无非是链表的遍历，增加，删除等，学过《数据结构》课程的人应该很容易看懂。
2.1分配内存
18840 PUBLIC phys_clicks alloc_mem(clicks)
18841 phys_clicks clicks; /* 要分配的内存块的大小 */
18842 {
18843 /* Allocate a block of memory from the free list using first fit. The block
18844 * consists of a sequence of contiguous bytes, whose length in clicks is
18845 * given by 'clicks'. A pointer to the block is returned. The block is
18846 * always on a click boundary. This procedure is called when memory is
18847 * needed for FORK or EXEC.
18848 */
18849
18850 register struct hole *hp, *prev_ptr;
18851 phys_clicks old_base;
18852
18853 hp = hole_head;/*从链表头开始遍历*/
18854 while (hp != NIL_HOLE) {
18855 if (hp->h_len >= clicks) {
18856 /* We found a hole that is big enough. Use it. */
18857 old_base = hp->h_base; /* 记下老的基地址 */
18858 hp->h_base += clicks; /* 修改空洞的基地址 */
18859 hp->h_len -= clicks; /* 修改空洞的长度*/
18860
18861 /* 如果空洞没有用完，直接返回，old_base 就是所求*/
18862 if (hp->h_len != 0) return(old_base);
18863
18864 /* 整个空洞都用完了，把该空洞放到一个free list中*/
18865 del_slot(prev_ptr, hp);
18866 return(old_base);
18867 }
18868
18869 prev_ptr = hp;
18870 hp = hp->h_next;
18871 }
18872 return(NO_MEM);
18873 }
代码比较简单，从空洞列表的头开始遍历，找到一个足够大小的空洞，修改空洞的基地址和长度，值得注意的是del_slot函数：
18926 PRIVATE void del_slot(prev_ptr, hp)
18927 register struct hole *prev_ptr; /* pointer to hole entry just ahead of 'hp' */
18928 register struct hole *hp; /* pointer to hole entry to be removed */
18929 {
18930 /* Remove an entry from the hole list. This procedure is called when a
18931 * request to allocate memory removes a hole in its entirety, thus reducing
18932 * the numbers of holes in memory, and requiring the elimination of one
18933 * entry in the hole list.
18934 */
18935
18936 if (hp == hole_head)
18937 hole_head = hp->h_next;
18938 else
18939 prev_ptr->h_next = hp->h_next;
18940
18941 hp->h_next = free_slots;
18942 free_slots = hp;
18943 }
这段代码的含义是把hp所指向的空洞从空洞链表中删除，这是基本的链表操作。然后把hp加到free_slots的头部，这时候大家应该明白free_slots的含义了，它指向一个链表的头部，这个链表保存了一系列的空洞，这些空洞的特点是：已经没有可以分配的空间，或者说其h_len域为0，实际上是一个空的数据结构。下面我们还会看到free_slots的用法。
2.2释放内存
18879 PUBLIC void free_mem(base, clicks)
18880 phys_clicks base; /* 要释放的内存块的基地址 */
18881 phys_clicks clicks; /* 要释放的内存块的长度*/
18882 {
18883 /* Return a block of free memory to the hole list. The parameters tell where
18884 * the block starts in physical memory and how big it is. The block is added
18885 * to the hole list. If it is contiguous with an existing hole on either end,
18886 * it is merged with the hole or holes.
18887 */
18888
18889 register struct hole *hp, *new_ptr, *prev_ptr;
18890
18891 if (clicks == 0) return;
18892 if ( (new_ptr = free_slots) == NIL_HOLE) panic("Hole table full", NO_NUM);
18893 new_ptr->h_base = base;
18894 new_ptr->h_len = clicks;
18895 free_slots = new_ptr->h_next;
/*18891至18895行：把free_slots链表上第一个空洞取下来，使其基地址和长度为要释放的值，并把free_slots后移到下一个元素*/
18896 hp = hole_head;
18897
18898 /* new_ptr现在指向一个可以重新分配的空洞，下面需要把new_ptr所指的空洞放到空洞列表的合适位置。需要注意的空洞列表是按基地址从小到大排列的。*/
18901
18902 if (hp == NIL_HOLE || base <= hp->h_base) {
18903 /* 直接放到空洞列表的头部*/
18904 new_ptr->h_next = hp;
18905 hole_head = new_ptr;
18906 merge(new_ptr);
18907 return;
18908 }
18909
18910 /* 需要找到一个合适的位置 */
18911 while (hp != NIL_HOLE && base > hp->h_base) {
18912 prev_ptr = hp;
18913 hp = hp->h_next;
18914 }
18915
18916 /* 在prev_ptr后面插入新的空洞*/
18917 new_ptr->h_next = prev_ptr->h_next;
18918 prev_ptr->h_next = new_ptr;
18919 merge(prev_ptr); /* sequence is 'prev_ptr', 'new_ptr', 'hp' */
18920 }
在释放内存中用到了merge函数：
18949 PRIVATE void merge(hp)
18950 register struct hole *hp; /* ptr to hole to merge with its successors */
18951 {
/* 从hp指向的空洞开始，向后找两个空洞，如果这三个空洞是连续的（即一个空洞的基地址加长度等于后面那个空洞的基地址），则把这三个空洞合并*/
18958 register struct hole *next_ptr;
18959
18960 /* If 'hp' points to the last hole, no merging is possible. If it does not,
18961 * try to absorb its successor into it and free the successor's table entry.
18962 */
18963 if ( (next_ptr = hp->h_next) == NIL_HOLE) return;
18964 if (hp->h_base + hp->h_len == next_ptr->h_base) {
18965 hp->h_len += next_ptr->h_len; /* first one gets second one's mem */
18966 del_slot(hp, next_ptr);
18967 } else {
18968 hp = next_ptr;
18969 }
18970
18971 /* If 'hp' now points to the last hole, return; otherwise, try to absorb its
18972 * successor into it.
18973 */
18974 if ( (next_ptr = hp->h_next) == NIL_HOLE) return;
18975 if (hp->h_base + hp->h_len == next_ptr->h_base) {
18976 hp->h_len += next_ptr->h_len;
18977 del_slot(hp, next_ptr);
18978 }
18979 }
2.3获得最大空洞的大小
18985 PUBLIC phys_clicks max_hole()
18986 {
18987 /* Scan the hole list and return the largest hole. */
18988
18989 register struct hole *hp;
18990 register phys_clicks max;
18991
18992 hp = hole_head;
18993 max = 0;
18994 while (hp != NIL_HOLE) {
18995 if (hp->h_len > max) max = hp->h_len;
18996 hp = hp->h_next;
18997 }
18998 return(max);
18999 }
代码非常简单，不再解释。
2.4空洞初始化
19005 PUBLIC void mem_init(total, free)
19006 phys_clicks *total, *free; /* memory size summaries */
19007 {
19018 register struct hole *hp;
19019 phys_clicks base; /* base address of chunk */
19020 phys_clicks size; /* size of chunk */
19021 message mess;
19022
19023 /* 先形成一个链表，让free_slots指向表头，hole_head则指向NULL */
19024 for (hp = &hole[0]; hp < &hole[NR_HOLES]; hp++) hp->h_next = hp + 1;
19025 hole[NR_HOLES-1].h_next = NIL_HOLE;
19026 hole_head = NIL_HOLE;
19027 free_slots = &hole[0];
/* 下面的循环不断的向内核发送消息，获取物理内存的信息 */
19033 *free = 0;
19034 for (;;) {
19035 mess.m_type = SYS_MEM;
19036 if (sendrec(SYSTASK, &mess) != OK) panic("bad SYS_MEM?", NO_NUM);
19037 base = mess.m1_i1;
19038 size = mess.m1_i2;
19039 if (size == 0) break; /* no more? */
19040
19041 free_mem(base, size); /*注意，这里的每次释放最终会形成一个空洞链表*/
19042 *total = mess.m1_i3;
19043 *free += size;
19044 }
19045 }
说明：由于MM和内核是分开的，他们之间只能利用消息来通信，mem_init中sendrec(SYSTASK, &mess)含义是向SYSTASK发送一条消息，获取一块内存信息，Minix最终会调用下面的函数：
15424 PRIVATE int do_mem(m_ptr)
15425 register message *m_ptr; /* pointer to request message */
15426 {
15427 /* Return the base and size of the next chunk of memory. */
15428
15429 struct memory *memp;
15430
15431 for (memp = mem; memp < &mem[NR_MEMS]; ++memp) {
15432 m_ptr->m1_i1 = memp->base;
15433 m_ptr->m1_i2 = memp->size;
15434 m_ptr->m1_i3 = tot_mem_size;
15435 memp->size = 0;
15436 if (m_ptr->m1_i2 != 0) break; /* found a chunk */
15437 }
15438 return(OK);
15439 }
注意：do_mem函数每次都会找到一块size不为0的内存返回，它把基地址写到乐m1_i1域中，把长度写到了m1_i2中，把总的内存大小写到了m1_i3域中，这样mem_init就可以读取。
后面我们将会看到更多的利用消息和内核打交道的代码。
