Linux Stuff

BSS 段： BSS 段（ bss segment ）通常是指用来存放程序中未初始化的全局变量的一块内存区域。 BSS 是英文 Block Started by Symbol 的简称。 BSS 段属于静态内存分配。 数据段： 数据段（ data segment ）通常是指用来存放程序中已初始化的全局变量的一块内存区域。数据段属于静态内存分配。 代码段： 代码段（ code segment/text segment ）通常是指用来存放程序执行代码的一块内存区域。这部分区域的大小在程序运行前就已经确定，并且内存区域通常属于只读 , 某些架构也允许代码段为可写，即允许修改程序。在代码段中，也有可能包 含一些只读的常数变量，例如字符串常量等。 堆（ heap ）： 堆是用于存放进程运行中被动态分配的内存段，它的大小并不固定，可动态扩张或缩减。当进程调用 malloc 等函数分配内存时，新分配的内存就被动态添加到堆上（堆被扩张）；当利用 free 等函数释放内存时，被释放的内存从堆中被剔除（堆被缩减） 栈 (stack) ：栈又称堆栈， 是用户存放程序临时创建的局部变量，也就是说我们函数括弧“ {} ”中定义的变量（但不包括 static 声明的变量， static 意味着在数据段中存放变量）。除此以外，在函数被调用时，其参数也会被压入发起调用的进程栈中，并且待到调用结束后，函数的返回值也会被存放回栈中。由于栈的先进先出特点，所以栈特别方便用来保存 / 恢复调用现场。从这个意义上讲，我们可以把堆栈看成一个寄存、交换临时数据的内存区。 这段时间忙过去后，把Linux用户空间中各个段对应的线性地址分布画出来。先MARK一下。

alloc_pages()函数用来给进程分配块，分配块所用的就是伙伴算法。 如果给进程分配块，调用的是get_page_from_freelist()。在分配块的过程中，我们要实施一些策略，也就是，假如可用内存的数量不足的话，要回收一些内存。我们在上一次的物理内存管理的pglist_data的数据结构也看到了，用于异步回收的进程。 在《深入理解Linux虚拟内存管理》的书中，有这样的一幅图： 这幅图中我们可以看到，在那些时候唤醒kswapd来进行异步回收内存，什么时候，同步回收内存。 其实alloc_pages()就是围绕着这幅图来设计算法的。 分配的具体步骤是： 1、用page_low作为阈值（就是分配结束后，要最少还有page_low数量的内存存在），来进行分配。如果分配成功，很好。如果分配不成功，那么就唤醒kswapd()来进行异步回收内存。 2、第一个步骤里面其实已经在某种程度上达到我们的目的了。也就是能够控制内存分配的速度了。因此，降低阈值。同时，还要看一下进程要求分配内存的分配策略，假若进程是非中断处理程序的实时进程，或者该进程不能被阻塞，那么这个时候，我要在最低阈值的标准的基础上，再次降低阈值，即page_min-=page-min/4。如果进程要求分配进程的策略还有加强，那么继续减小阈值：page_min-=page_min/2。阈值减小后，再次进行分配。 3、如果第二步分配成功了，不错；如果没有分配成功，那么就比较麻烦了。就需要启动同步回收内存的机制了。但在启动同步内存回收之前，我们要看一下进程的属性，假若进程本身是正在分配内存，或者进程正在撤销以释放内存，那么就需要特殊对待了，如果分配策略允许，就不再设置阈值，直接分配。如果没有分配成功，看一下，这个进程是不是很特殊，如果它不允许分配失败，就要不停的循环，不停的去尝试，直到分配成功。反之，分配失败，就不再往下尝试了。因为，在这里，进程本身就是回收内存，或者进程本身就在撤销以释放内存，这已经是底线了。 4、第3步，是一个特殊的情况 。那么对于一般的进程在第二步较低阈值的情况下仍然没有分配成功，就开始同步回收内存了。方法就是把进程的标志位设置为PF_MEMALLOC,然后把进程回收的状态也改变了，对于不再活跃的SLAB也给回收了。然后就开始同步回收内存了。注意，这里同步回收的话，进程实际上是被阻塞的，

对于内存管理来讲，包括两个方面，一个是物理内存的管理，另一个是线性地址空间的管理。物理内存的管理是从“供应”的角度来看，我现在仓库里面有多少资源可以供分配，而线性地址空间的管理，则是从“需求”的角度去考虑，我需要多少的线性地址空间来满足进程的运行。把供应和需求连接起来的纽带就是缺页调用，以及页面的分配了。 下面从“供应”的角度谈谈，Linux系统如何来管理有限的物理内存资源的。 以I386为例，我们都知道，系统启动的时候，Bios检索内存，检查一下本机的物理内存有多大MB，对于CPU里面的MMU来讲，在寻址的时候，以4KB的页面来进行页面寻址的，既是每一个页面的大小为4KB，当然，如果是2MB的话，每一个页面大小就是2MB了，同样道理，某些I386CPU也支持4MB和1GB大小的页面，我们现在假定以4KB为例。以4KB为例，操作系统把全部的物理内存以4KB来分割，进行管理，在给进程分配的时候，最小的单位是1页，而进行SWAP和回收的时候 ，也是以最小的页为单位来进行处理的。因此，就需要有一个数据结构来描述一个物理页面的状态了： 1、  这个页面分配了么？也就是这个页面在使用中么？如果在使用，那么被几个进程使用了。 2、  这个页面被几个页表项映射了？ 这个也挺重要，因为，如果，这个页要是换出的话，得告诉自己的“顶头上司”映射自己的页表项。让他们有所改变才行。 3、  另外，如果页面被使用了，那么是存放的某些文件的内容，还是用于进程自己使用的？ 如果是某些文件的内容，那么标识一下，以后的其他进程使用的话，就直接在内存中读，而不需要舍近求远了。----这就是传说中的高速缓冲区 4、  这个页面内容如果存放的是某个文件的内容，那么页面存放的数据相对于文件头来讲，具体是那一部分的数据？ 这就是说，如果我要写回，我写到文件的什么位置捏？！ 5、  这个页面现在是被使用的么，还是暂时没有被使用？ 如果没有被使用，就可以分配给其他进程了，如果被使用了，那么就不能给别的进程映射了。 由了这里的分析，那么我们就看一下Linux系统是怎样来描述一个物理页的状态的吧： 223 struct page { 224     unsigned long flags;        /* Atomic flags, some possibly 225                      *

凡是调用 do_wp_page ，一定满足的条件是，要写一个只读的页。这里的写，是一次用户进程的操作，从 handle_pte_fault 的最后一个参数 write_access 来的。而对于只读的页，则是因为页框受保护的，而进程所辖属的 vm_area_struct 里面的标志一定是可写的，如果不可写，而进程要求可写，那么早已经在 do_page_fault 里面进入 bad_area 代码块处理去了（在这个代码块的具体操作是 Kill 进程），看一下： 463 case 2: /* write, not present */ 464 if (!(vma->vm_flags & VM_WRITE)) 465 goto bad_area; 466 write++;//vma write 467 break; 那么从哪里判断是只读的页，然后出现缺页异常呢？ 答曰：从 pte 的 flags 字段的相关属性来判断。在 fork 进程的时候已经订好了什么样的页写了保护。真的吗 ? 真的！请看： 在 fork 一个进程的时候，会调用 copy_one_pte(), 在这个函数里面是这样处理进程间共享页面的： mm/memory.c 467 if (is_cow_mapping(vm_flags)) { 468 ptep_set_wrprotect(src_mm, addr, src_pte); 469 pte = *src_pte; 470 } 因此，对于按需调页的，一定会触发缺页异常，然后 COW. 下面，让我们来看一下对于写一个只读的页，是 Linux 是怎样来处理的吧： 1 、首先获得发生写异常时候的页描述符，通过 vm_normal_page() 函数来获得，这个函数的功能：就是如果有页描述符，就返回页描述符；如果没有页描述符，那么就返回 NULL 。（为什么会没有页描述符呢？我们不是说每一个 4K 的页面不都是与 struct page 数据结构相对应的么？让我们来看一下 vm_normal_page() 函数前面的注释吧： 370 * NOTE! Some mappings do not have "struct pages". A raw PFN mapping 371 * will have

在我的机器上运行free命令： root@Localhost:/home/hayfeng# free              total       used       free     shared    buffers     cached Mem:        153832     141612      12220          0      17340      94580 -/+ buffers/cache:      29692     124140 Swap:       281096      10432     270664 第一行： total = used + free      |  153832 = 141612 + 12220 第二行： -buffers/cache(代表用户程序使用的空间，不包括内核为用户线程加载的文件映射)：    = used - ( buffers + cached )   |   29692 = 141612 - ( 17340 + 94580 ) +buffers/cache(代表用户进程可以使用的空间)，当然内核映射的线性文件也可以映射给用户进程，因此：    = free + ( buffers + cached )   |  124140 = 12220 + ( 17340 + 94580 ) ----- 从上面的-buffers/cache 和 + buffers/cache 来看，buffers和cached是属于内核的，但可以被用户进程使用。因此： 1、计算用户进程所使用的物理内存时的计算方法是：已经用掉的内存总量减去buffers和cached。(哎，难道内核线程不需要私有内存了？) 2、计算用户进程所能够使用物理内存时的计算方法是：可用的物理内存总量加上buffers和cached。因为内核映射的物理内存可以被用户进程共享嘛。 这些东西，会者不难，难者不会啊！ 该文章讨论贴： http://www.linuxforum.net/forum/showflat.php?Cat=&Board=linuxK&Number=747039&page=0&view=expanded&sb=5&o=7&fpart=

Red/Black Tree Demonstration: Maintenance Version 转自： http://peterpannju.blogbus.com/logs/21992610.html     红黑树是个复杂的数据结构。其插入，删除操作复杂度都为O(lgn)。     红黑树在 linux 内核中应用很多，比如虚拟内存管理，进程调度等。且其常常和 hash 一起出现，是非常重要的数据结构。 Contents:   Defination of Red-Black Tree   Insertion   Deletion   Comparison with BST & AVL   Red-Black Tree Demonstration   Defination of Red-Black Tree As defined in CLRS, a red-black tree is a binary search tree (BST) that satisfies the following properties: Every node is either red or black. The root is black. Every leaf (NIL) is black. If a node is red, then both its children are black. (Or in other words, two red nodes may not be adjacent.) For each node, all paths from the node to descendant leaves contain the same number of black nodes.     红黑树的数据并不存储在叶节点上。叶节点全部是 NIL。这可以帮助红黑树插入删除操作。 红黑树的高度不超过2lg(n+1)。证明请参考 CLRS。 Insertion     红黑树的插入方法有两种。分别为 Okasaki's Insertion Method 和 CLRS Insertion Method。CLRS给出的方法比 Okasaki 的更复杂，但是效率较高。这里，我们采用 CLRS 中所采用的方法。   static   void

在linux下每个系统调用由两部分组成： （1）：核心函数：是实现系统调用功能的代码，作为操作系统的核心驻留在内存中，是一种共享代码。运行在核心态。 （2）：接口函数：是提供给应用程序的API,以库函数的形式存在于linux的lib.a中，该库中存放了所有系统调用的接口函数的目标代码，用汇编语言书写。其主要功能是把系统调用号，入口参数地址传给相应的核心函数，并使用户态下运行的应用程序陷入核心态。 以下转自：http://hi.baidu.com/cwt0408/blog/item/fd53924c19d5a8f1d62afcea.html 系统调用和普通库函数调用： linux内核中设置了一组用于实现系统功能的子程序，成为系统调用。系统调用和普通库函数调用非常相似，只是系统调用由操作系统核心提供，运行于核心态，而普通的函数调用由函数库或用户自己提供，运行于用户态。 如何工作： 一般的，进程是不能访问内核的。它不能访问内核所占内存空间也不能调用内核函数。CPU硬件决定了这些（这就是为什么它被称作"保护模式"）。系统调用是这些规则的一个例外。其原理是进程先用适当的值填充寄存器，然后调用一个特殊的指令，这个指令会跳到一个事先定义的内核中的一个位置（当然，这个位置是用户进程可读但是不可写的）。在Intel CPU中，这个由中断0x80实现。硬件知道一旦你跳到这个位置，你就不是在限制模式下运行的用户，而是作为操作系统的内核--所以你就可以为所欲为。 进程可以跳转到的内核位置叫做sysem_call。这个过程检查系统调用号，这个号码告诉内核进程请求哪种服务。然后，它查看系统调用表 (sys_call_table)找到所调用的内核函数入口地址。接着，就调用函数，等返回后，做一些系统检查，最后返回到进程（或到其他进程，如果这个进程时间用尽）。如果你希望读这段代码，它在<内核源码目录>/kernel/entry.S，Entry(system_call)的下一行。 什么是errno： 为防止和正常的返回值混淆，系统调用并不直接返回错误码，而是将错误码放入一个名为errno的全局变量中。如果一个系统调用失败，你可以读出errno的值来确定问题所在。 errno不同数值所代表的错误消息定义在errno.h中，你也可以通过命令"man 3 errno

转自： http://www.lupaworld.com/386879/viewspace-139248.html 本文档描述的是Xen hypervisor的宏观体系结构、辅助工具以及构建一个完整虚拟化环境所需的应用程序。本文的综合介绍了基于Xen3.2（2008年1月）的Xen体系结构，更详尽的描述请参考Xen books。 Xen组成要素 一个Xen虚拟化环境由以下相互配合的元素构成： Xen Hypervisor Domain 0 Domain管理和控制工具 Domain U PV客户系统 Domain U HVM客户系统 下面的图形是对这些要素基本组织的描述 Xen Hypervisor Xen Hypervisor是一个介于硬件和操作系统之间的软件层，它负责在各虚拟机之间进行CPU调度和内存分配（partitioning）。Xen Hypervisor不仅抽象出硬件层，同时控制虚拟机的执行，因为这些虚拟机共享同一个处理环境。Xen Hypervisor不会处理网络、存储设备、视频以及其他I/O。 Domain 0 Domain 0是一个修改过的Linux kernel，是唯一运行在Xen Hypervisor之上的虚拟机，它拥有访问物理I/O资源的权限，同时和系统上运行的其他虚拟机进行交互。Domain 0需要在其它Domain启动之前启动。 Domain 0中包含两个驱动：Network Backend Driver和Block Backend Driver，分别负责处理来自Domain U的网络和本地磁盘请求。Network Backend Driver直接和本地网络硬件进行通信以处理所有来自Domain U上客户操作系统的网络请求。Block Backend Driver和本地存储设备进行通信以处理来自Domain U的读写请求。 Domain U 运行在Xen Hypervisor上的所有半虚拟化（paravirtualized）虚拟机被称为“Domain U PV Guests”，其上运行着被修改过内核的操作系统，如Linux、Solaris、FreeBSD等其它UNIX操作系统。所有的全虚拟化虚拟机被称为“Domain U HVM Guests”，其上运行着不用修改内核的操作系统，如Windows等。 Domain U PV Guests的