Zhaoyuan's profile备忘纪事PhotosBlogListsMore  |  Tools Help |
|
April 24 Linux Memory Management(0.11 release)<4>以前写C code时经常会用malloc和free来动态申请和释放内存，但对操作系统是如何实现这个功能的却不知道，看了Linux 0.11的kernel code，总算知道是怎么回事了。
Linux 0.11中，使用桶描述符来管理动态内存，每个桶描述符管理一页内存，该页内存中分成指定大小的块，数据结构如下:
struct bucket_desc { /* 16 bytes */
void *page; //物理页内存的头指针 struct bucket_desc *next; //链向下一个桶 void *freeptr; //桶中空闲块的指针 unsigned short refcnt; //引用counter unsigned short bucket_size; //目前这一个桶中每个块的大小 }; 为了加速的分配和回收，定义一个桶目录，保存一组桶指针.
struct _bucket_dir { /* 8 bytes */
int size; struct bucket_desc *chain; }; 并如下初始化
struct _bucket_dir bucket_dir[] = {
{ 16, (struct bucket_desc *) 0}, { 32, (struct bucket_desc *) 0}, { 64, (struct bucket_desc *) 0}, { 128, (struct bucket_desc *) 0}, { 256, (struct bucket_desc *) 0}, { 512, (struct bucket_desc *) 0}, { 1024, (struct bucket_desc *) 0}, { 2048, (struct bucket_desc *) 0}, { 4096, (struct bucket_desc *) 0}, { 0, (struct bucket_desc *) 0}}; /* End of list marker */ 下面就可以看内核是如何申请内存的了。
void *malloc(unsigned int len)
{ struct _bucket_dir *bdir; struct bucket_desc *bdesc; void *retval; /*
* First we search the bucket_dir to find the right bucket change * for this request. */ for (bdir = bucket_dir; bdir->size; bdir++) if (bdir->size >= len) break; //找到一个块大小最合适的桶. if (!bdir->size) { printk("malloc called with impossibly large argument (%d)\n", len); panic("malloc: bad arg"); } /* * Now we search for a bucket descriptor which has free space */ cli(); /* Avoid race conditions */ for (bdesc = bdir->chain; bdesc; bdesc = bdesc->next) if (bdesc->freeptr) break; //找到该桶中一个空闲的快的头指针 /* * If we didn't find a bucket with free space, then we'll * allocate a new one. */ if (!bdesc) { //如果没有合适的桶. char *cp;
int i; if (!free_bucket_desc) //如果桶空的话，或者一页的桶描述符已经用完.
init_bucket_desc(); //该函数会申请一页内存，然后放入桶链表，所以这一页都是桶描述符. bdesc = free_bucket_desc; //free_bucket_desc总是当前空闲的桶描述符,这里就是把空闲的桶拿来处理 free_bucket_desc = bdesc->next; //free_bucket_desc则指向了下一个空闲的桶描述符 bdesc->refcnt = 0; bdesc->bucket_size = bdir->size; bdesc->page = bdesc->freeptr = (void *) cp = get_free_page(); //申请一页 if (!cp) panic("Out of memory in kernel malloc()"); /* Set up the chain of free objects */ for (i=PAGE_SIZE/bdir->size; i > 1; i--) { *((char **) cp) = cp + bdir->size; //非常有技巧的地方,自己领会吧. cp += bdir->size; } *((char **) cp) = 0; bdesc->next = bdir->chain; /* OK, link it in! */ bdir->chain = bdesc; //把这个桶描述符链上.. } retval = (void *) bdesc->freeptr; bdesc->freeptr = *((void **) retval); bdesc->refcnt++; sti(); /* OK, we're safe again */ return(retval); } April 22 Linux Memory Management(0.11 release)<3>一个进程的内存占用情况,从底到高依次是代码，数据，堆和堆栈。
下面看下缺页中断处理函数.
void do_no_page(unsigned long error_code,unsigned long address)
{ int nr[4]; unsigned long tmp; unsigned long page; int block,i; address &= 0xfffff000;
tmp = address - current->start_code; //计算出引发缺页中断的线性地址与当前task的代码起始地的offset. if (!current->executable || tmp >= current->end_data) { //第一个条件，如果但前进程还没有任何可执行代码，则直接分配内存， get_empty_page(address); //第二个条件，如果这个offset超过了进程的数据段，即进入了堆区，认为代码进行了申请了动态存 存,如malloc(sizeof(INT)),则直接分配内存。
return; }
if (share_page(tmp)) //到这里，说明该地址在进程的代码和数据段内，所以要挖掘潜在的内存共享。(如子进程共享父进程的代码和数据段).试图共享一页物理内存。 return; if (!(page = get_free_page())) //惨了，没有共享到，就只好申请一页内存，并从文件中读取数据出来。 oom(); /* remember that 1 block is used for header */ block = 1 + tmp/BLOCK_SIZE; for (i=0 ; i<4 ; block++,i++) nr[i] = bmap(current->executable,block); bread_page(page,current->executable->i_dev,nr); i = tmp + 4096 - current->end_data; tmp = page + 4096; while (i-- > 0) { tmp--; *(char *)tmp = 0; } if (put_page(page,address)) return; free_page(page); oom(); } 在这里面有做内存共享的动作，即share_page();
一个进程在创建时，都是先共享父进程的代码和数据段，被共享的内存页，属性会变为只读，而当父进程或子进程中任何一个试图去写该内存页时，即发生内存写保护错误，系统调用do_wp_page()进行处理
void do_wp_page(unsigned long error_code,unsigned long address)
{ #if 0 /* we cannot do this yet: the estdio library writes to code space */ /* stupid, stupid. I really want the libc.a from GNU */ if (CODE_SPACE(address)) do_exit(SIGSEGV); #endif un_wp_page((unsigned long *) (((address>>10) & 0xffc) + (0xfffff000 & *((unsigned long *) ((address>>20) &0xffc))))); //传递的参数，页表项指针 }
void un_wp_page(unsigned long * table_entry)
{ unsigned long old_page,new_page; old_page = 0xfffff000 & *table_entry;
if (old_page >= LOW_MEM && mem_map[MAP_NR(old_page)]==1) { *table_entry |= 2; invalidate(); return; } if (!(new_page=get_free_page())) //申请一页新的物理内存 oom(); if (old_page >= LOW_MEM) mem_map[MAP_NR(old_page)]--; *table_entry = new_page | 7; //加属性后赋给该页表项 invalidate(); copy_page(old_page,new_page); //将共享物理页面的内容，复制给新的物理页 } 可以看出，父子进程，谁先触发了页保护中断(和缺页是一个中断),谁就会获得新的一个物理页面。
再看页表拷贝函数,在fork.c中进程创建时调用，用于实现父子进程的内存共享。
int copy_page_tables(unsigned long from,unsigned long to,long size)
{ unsigned long * from_page_table; unsigned long * to_page_table; unsigned long this_page; unsigned long * from_dir, * to_dir; unsigned long nr; if ((from&0x3fffff) || (to&0x3fffff)) //一个页表管理4M内存， panic("copy_page_tables called with wrong alignment"); from_dir = (unsigned long *) ((from>>20) & 0xffc); /* _pg_dir = 0 */ //获取源页目录表项 to_dir = (unsigned long *) ((to>>20) & 0xffc); //目的页目录表项 size = ((unsigned) (size+0x3fffff)) >> 22; //计算需要copy几个页表 for( ; size-->0 ; from_dir++,to_dir++) { if (1 & *to_dir) panic("copy_page_tables: already exist"); if (!(1 & *from_dir)) continue; from_page_table = (unsigned long *) (0xfffff000 & *from_dir); //源页表地址 if (!(to_page_table = (unsigned long *) get_free_page())) //为目的页表申请一页内存 return -1; /* Out of memory, see freeing */ *to_dir = ((unsigned long) to_page_table) | 7; //加上属性赋给目的页表项 nr = (from==0)?0xA0:1024; for ( ; nr-- > 0 ; from_page_table++,to_page_table++) { //此循环逐个copy页表项，并改变页的属性为只读 this_page = *from_page_table; if (!(1 & this_page)) continue; this_page &= ~2; *to_page_table = this_page; if (this_page > LOW_MEM) { *from_page_table = this_page; this_page -= LOW_MEM; this_page >>= 12; mem_map[this_page]++; // } } } invalidate(); return 0; } Linux Memory Management (0.11 release) <2>接着上篇说，Linux kernel init时的task0, 使用了4个内核的页表，当应用程序运行的时候,其页表既是通过调用 void get_empty_page(unsigned long address) if (!(tmp=get_free_page()) || !put_page(tmp,address)) { 来获得.注意此页表已经是存放在主内存区的，不同于内核使用的四个页表，他们四个是固定放在物理内存0x1000,0x2000,x03000,0x4000处的，每个页表顺序映射4M物理内存，这样内核使用的线性地址等于实际的物理地址。 那么进程的4G(0x0000 0000 ~ 0xFFFF FFFF)线性地址是如何映射到16M(0x000 000~ 0xFFF FFF) 物理内存上去的呢？ 接着上一篇的例子来说,逻辑地址：21h:12345678h转换为线性地址即为0x23456789h 由于进程在创建时，并不会把其会访问到的内存全部装入，而是在进程访问到该地址时才动态载入，这样必然导致第一次访问该地址出时，其所在页面不在内存中，触发缺页中断，系统最终会通过get_empty_page(0x23456789)来获取一页物理内存并建立和0x23456789的映射。 a. 假定里面的get_free_page()获取的物理内存页地址为 0x123 000。 a. put_page(0x123 000,0x23456789)来建立映射，线性地址0x23456789的高10bit为0x0010 0011 01 ,即为页目录表的索引值(140) b. 该索引处的页目录表项的值高20bit不在内存，说明没有页表，需要再申请一页物理内存(假定获取的页面物理址在0xf10 000)用于存放页表，到此，这一页表即将对应从0x234x xxxx开始的4M线性内存. 将这页内存的地址加上访问属性后(0xf10 007)填入该页目录表项中。 c. 接着获取线性地址的中间10bit. 0x00 0101 0110=0x56，得到页表的偏移地址，加上页表的基址0xf10 000= 0xf10 056，此即为该线性地址对应的页表项地址，将 0x123 000 加上属性(0x123 007)填入到0xf10 056处，至此整个映射结束。 d. 对线性地址0x23456789 的访问，通过2级页表找到了它映射到的物理内存页面0x123 000, 然后取线性地址的低12位0x789,得到最终的物理内存 0x123 789。 这样以后对0x23456000 ~ 0x23456FFF的访问就是访问物理内存0x123 000~ 0x123 FFF。 这时，进程如果访问0x234FF789的线性地址，由于该页不再内存，而再次调用get_free_page() 1. 假定里面的get_free_page()获取的物理内存页地址为 0x234 000。 2. 由于此时0x234FF789对应的页目录项中的内存有效，即页表存在，所以只须，取0x234FF789的中间10bit来定位到具体的页表项，0xFF，加上页表的基址0xf10 000= 0xf10 0FF，此即为该线性地址对应的页表项地址，将 0x234 000 加上属性(0x234 007)填入到0xf10 0FF处完成本次映射。 3.至此，对0x234FF789的访问，通过2级页表找到了它映射到的物理内存页面0x234 000, 然后取线性地址的低12位0x789,得到最终的物理内存 0x234 789。 这样以后对0x234FF000 ~ 0x234FFFFF的访问就是访问物理内存0x234 000~ 0x234 FFF。 可见，进程的连续线性地址最终在物理内存上是按页分开，独立的。 显然4G的线性空间比16M大了很多，所以系统会尽量挖掘共享内存，如果还出现内存页面不够，则通过二级存储空间进行swap，将暂时不使用的页面调出，然后将这页分配出去。
April 21 80386保护模式下的内存访问(ZZ)1.分段机制 80386的两种工作模式 80386的工作模式包括实地址模式和虚地址模式（保护模式）。Linux主要工作在保护模式下。 分段机制 在保护模式下，80386虚地址空间可达16K个段，每段大小可变，最大达4GB。 从逻辑地址到线性地址的转换由80386分段机制管理。段寄存器CS、DS、ES、SS、FS或GS标识一个段。这些段寄存器作为段选择器，用来选择该段的描述符。 分段逻辑地址到线性地址转换图
 图1 分段逻辑地址到线性地址转换图
2. 分页机制 分页机制的作用 分页机制是在段机制之后进行的，它进一步将线性地址转换为物理地址。 80386使用4K字节大小的页，且每页的起始地址都被4K整除。因此，80386把4GB字节线性地址空间划分为1M个页面，采用了两级表结构。 两级页表 两级表的第一级表称为页目录，存储在一个4K字节的页中，页目录表共有1K个表项，每个表项为4个字节，线性地址最高的10位（22-31）用来产生第一级表索引，由该索引得到的表项中的内容定位了二级表中的一个表的地址，即下级页表所在的内存块号。 第二级表称为页表，存储在一个4K字节页中，它包含了1K字节的表项，每个表项包含了一个页的物理地址。二级页表由线性地址的中间10位（12-21）位进行索引，定位页表表项，获得页的物理地址。页物理地址的高20位与线性地址的低12位形成最后的物理地址。 利用两级页表转换地址
 图2 利用两级页表转换地址
3. 内核空间和用户空间
用户空间 在Linux中，每个用户进程都可以访问4GB的线性虚拟内存空间。其中从0到3GB的虚存地址是用户空间，用户进程可以直接访问。 内核空间 从3GB到4GB的虚存地址为内核态空间，存放供内核访问的代码和数据，用户态进程不能访问。所有进程从3GB到4GB的虚拟空间都是一样的，linux以此方式让内核态进程共享代码段和数据段。
保护模式（1）---存储方式 Writen By Dangerman 保护模式现代操作系统的基础，理解他是我们要翻越的第一座山。保护模式是相对实模式而言的，他们是处理器的两种工作方式。很久以前大家使用的dos就是运行在实模式下，而现在的windows操作系统则是运行在保护模式下。两种运行模式有着较大的不同， 实模式由于是由8086/8088发展而来因此他更像是一个运行单片机的简单模式，计算机启动后首先进入的就是实模式，通过8086/8088只有20根 地址线所以它的寻址范围只有2的20次幂，即1M。内存的访问方式就是我们熟悉的seg:offset逻辑地址方式，例如我们给出地址逻辑地址它将在 cpu内转换为20的物理地址，即将seg左移4位再加上offset值。例如地址1000h:5678h，则物理地址为10000h+5678h= 15678h。实模式在后续的cpu中被保留了下来，但实模式的局限性是很明显的，由于使用seg:offset逻辑地址只能访问1M多一点的内存空间， 在拥有32根地址线的cpu中访问1M以上的空间则变得很困难。而且随着计算机的不断发展实模式的工作方式越来越不能满足计算机对资源（存储资源和cpu 资源等等）的管理，由此产生了新的管理方式——保护模式。 80386及以上的处理器功能要大大超过其先前的处理器，但只有在保护模式下，处理器才能发挥作用。在保护模式下，全部32根地址线有效，可寻址4G的物 理地址空间；扩充的存储分段机制和可选的存储器分页机制，不仅为存储器共享和保护提供了硬件支持，而且为实现虚拟存储器提供了硬件支持；支持多任务；4个 特权级和完善的特权级检查机制，实现了数据的安全和保密。计算机启动后首先进入的就是实模式，通过设置相应的寄存器才能进入保护模式（以后介绍）。保护模式是一个整体的工作方式，但分步讨论由浅入深更利于学习。 一．存储方式 存储方式主要体现在内存访问方式上，由于兼容和IA32框架的限制，保护模式在内存访问上延用了实模式下的seg:offset的形式（即：逻辑地址）， 其实seg:offset的形式在保护模式下只是一个躯壳，内部的存储方式与实模式截然不同。在保护模式下逻辑地址并不是直接转换为物理地址，而是将逻辑 地址首先转换为线性地址，再将线性地址转换为物理地址。如图一：
线性地址是个新概念，但大家不要把它想的过于复杂，简单的说他就是0000000h~ffffffffh(即0~4G)的线性结构，是32个bite位能 表示的一段连续的地址，但他是一个概念上的地址，是个抽象的地址，并不存在在现实之中。线性地址地址主要是为分页机制而产生的。处理器在得到逻辑地址后首 先通过分段机制转换为线性地址，线性地址再通过分页机制转换为物理地址最后读取数据。如图二：
分段机制是必须的，分页机制是可选的，当不使用分页的时候线性地址将直接映射为物理地址，设立分页机制的目的主要是为了实现虚拟存储（分页机制在后面介绍）。先来介绍一下分段机制，以下文字是介绍如何由逻辑地址转换为线性地址。 分段机制在保护模式中是不能被绕过得，回到我们的seg:offset地址结构，在保护模式中seg有个新名字叫做“段选择子”（seg.. selector）。段选择子、GDT、LDT构成了保护模式的存储结构，如图三`，GDT、LDT分别叫做全局描述符表和局部描述符表，描述符表是一个 线性表（数组），表中存放的是描述符。
“描述符”是保护模式中的一个新概念，它是一个8字节的数据结构，它的作用主要是描述一个段（还有其他作用以后再说），用描述表中记录的段基址加上逻辑地 址(sel:offset)的offset转换成线性地址。描述符主要包括三部分：段基址（Base）、段限制（Limit）、段属性（Attr）。一个 任务会涉及多个段，每个段需要一个描述符来描述，为了便于组织管理，80386及以后处理器把描述符组织成表，即描述符表。在保护模式中存在三种描述符表 “全局描述符表”（GDT）、“局部描述符表”（LDT）和中断描述符表（IDT）(IDT在以后讨论)。 （1）全局描述符表GDT（Global Descriptor Table）在整个系统中，全局描述符表GDT只有一张，GDT可以被放在内存的任何位置，但CPU必须知道GDT的入口，也就是基地址放在哪里，Intel的设计者门提供了一个寄存器GDTR用来存放GDT的入口地址，程序员将GDT设定在内存中某个位置之后，可以通过LGDT指令将GDT的入口地址装入此积存器，从此以后，CPU就根据此寄存器中的内容作为GDT的入口来访问GDT了。GDTR中存放的是GDT在内存中的基地址和其表长界限。
（2）段选择子（Selector）由GDTR访问全局描述符表是通过“段选择子”（实模式下的段寄存器）来完成的，如图三①步。段选择子是一个16位的寄存器（同实模式下的段寄存器相同）如图四
段选择子包括三部分：描述符索引（index）、TI、请求特权级（RPL）。他的index（描述符索引）部分表示所需要的段的描述符在描述符表的位 置，由这个位置再根据在GDTR中存储的描述符表基址就可以找到相应的描述符（如图三①步）。然后用描述符表中的段基址加上逻辑地址（SEL: OFFSET）的OFFSET就可以转换成线性地址（如图三②步），段选择子中的TI值只有一位0或1，0代表选择子是在GDT选择，1代表选择子是在 LDT选择。请求特权级（RPL）则代表选择子的特权级，共有4个特权级（0级、1级、2级、3级）。 例如给出逻辑地址：21h:12345678h转换 为线性地址 a. 选择子SEL=21h=0000000000100 0 01b 他代表的意思是：选择子的index=4即100b选择GDT中的第4个描述符；TI=0代表选择子是在GDT选择；左后的01b代表特权级RPL=1 b. OFFSET=12345678h若此时GDT第四个描述符中描述的段基址（Base）为11111111h，则线性地址=11111111h+12345678h=23456789h （3）局部描述符表LDT（Local Descriptor Table）局部描述符表可以有若干张，每个任务可以有一张。我们可以这样理解GDT和LDT：GDT为一级描述符表，LDT为二级描述符表。如图五
LDT和GDT从本质上说是相同的，只是LDT嵌套在GDT之中。LDTR记录局部描述符表的起始位置，与GDTR不同LDTR的内容是一个段选择子。由 于LDT本身同样是一段内存，也是一个段，所以它也有个描述符描述它，这个描述符就存储在GDT中，对应这个表述符也会有一个选择子，LDTR装载的就是 这样一个选择子。LDTR可以在程序中随时改变，通过使用lldt指令。如图五，如果装载的是Selector 2则LDTR指向的是表LDT2。 举个例子：如果我们想在表LDT2中选择第三个描述符所描述的段的地址12345678h。 a. 首先需要装载LDTR使它指向LDT2 使用指令lldt将Select2装载到LDTR b. 通过逻辑地址（SEL:OFFSET）访问时SEL的index=3代表选择第三个描述符；TI=1代表选择子是在LDT选择，此时LDTR指向的是 LDT2,所以是在LDT2中选择，此时的SEL值为1Ch(二进制为11 1 00b)。OFFSET=12345678h。逻辑地址为1C:12345678h c. 由SEL选择出描述符，由描述符中的基址（Base）加上OFFSET可得到线性地址，例如基址是11111111h，则线性地址=11111111h+12345678h=23456789h d. 此时若再想访问LDT1中的第三个描述符，只要使用lldt指令将选择子Selector 1装入再执行2、3两步就可以了（因为此时LDTR又指向了LDT1） 由于每个进程都有自己的一套程序段、数据段、堆栈段，有了局部描述符表则可以将每个进程的程序段、数据段、堆栈段封装在一起，只要改变LDTR就可以实现对不同进程的段进行访问。 存储方式是保护模式的基础，学习他主要注意与实模式下的存储模式的对比，总的思想就是首先通过段选择子在描述符表中找到相应段的描述符，根据描述符中的段基址首先确定段的位置，再通过OFFSET加上段基址计算出线性地址。 April 20 Linux Memory Management(0.11 release)<1>
当进程通过线性地址address访问内存时，如果出现缺页，则会触发缺页中断，内核经过一系列操作后，会申请出一页物理内存，并建立该页物理内存和线性地址的映射，供进程使用。 void get_empty_page(unsigned long address) if (!(tmp=get_free_page()) || !put_page(tmp,address)) { //get_freee_page()即可从主内存区获得一页物理内存,返回该页物理内存的头指针。 //put_page(tmp,address)即建立该物理页面与线性地址的映射。 unsigned long put_page(unsigned long page,unsigned long address) /* NOTE !!! This uses the fact that _pg_dir=0 */ //这里假定页目录表的在内存地址0x0处，不然页表的地址要加上相应的偏移地址，使程序复杂化 if (page < LOW_MEM || page >= HIGH_MEMORY) // page_table为线性地址address对应的页目录表项，即在页目录表中的索引，用于查找页表。 //获取该页表的物理地址 //根据线性地址的中间10bit，定位到页表项，然后将page和该页表项建立映射。 Linux内核在初始化时，会建立一个页目录表项和四个页表，其中也目录表是内核和其他进程公用的，但四个页表是内核独用的，可以映射16M内存。对于32位的x86体系结构，保护模式下使用的是段页式内存管理，代码段和数据段不是简单的段地址而是全局段描述符表中的index，每个表项占据8个字节，通过索引这个表，即可找到代码段和数据段的更详细的信息，包括特权级(保护模式的核心)，段的基址和限长等。 Linux内核的代码段和数据段的设定为 CS :0x00C0 9a00 0000 0fff //基址为0,段限长为16M DS: 0x00C0 9200 0000 0fff 可见，Linux内核中，逻辑地址即为线性地址,内核初始化四个内核页表的方法，则表明线性地址和实际物理地址一一对应，所以，内核使用的内存即为实际物理内存。 对于用户程序，系统会在主内存区申请一页内存来放页表，即会调用上面所说的get_empty_page，从主内存区获得一页内存。 |
|
|||||||
|
|
