一个进程可以分配多大的内存?

colddawn

那下一步的实验是不是就该想办法在各个系统上扩大Stack来观察盏增长情况以及最大值了？

congli

原帖由 zzbwang 于 2006-3-29 12:01 发表
大家讨论了半天，还是没有告诉BSD进程到底可以使用多大的内存空间啊。如果我在服务器上装了4GB内存，MAXDSIZ最大可以设置成多少不会出问题？可以设置成3800MB吗？

倒,兄弟认真看就知道

Alligator27

原帖由 雨丝风片 于 2006-3-29 10:08 发表



呵呵，反正就是个名字，叫什么还不都一样，。在没有特别注明的情况下，我所指的都是FreeBSD/NetBSD目前使用的malloc，作者为Poul-Henning Kamp。在这个malloc里，它的“page”定义为4K大小，它就是 ...

刚看了PHK malloc 和他写的 "Malloc Revisited". 你说的没错, PHK malloc 确实是mmap一块内存作page-directory. 他根据brk的值确定需要的page-directory的大小. 所以32bit进程大约要3GB/4KB*4Bytes=3MB. 考虑到不是一次分配, 6MB 的空间就够了. 一些shared libs在占一些mmap空间. 还是有一点对不上数.

PHK malloc 做得不错, 但有几点不好, 让我有点意外.
1 page-directory的大小是根据brk的值确定, 象LZ的测试程序是1MB的内存块, 与同样总内存但是1KB的内存块要分配同样大小的page-directory, 有点浪费.
2 brk() 失败后, 没有用mmap. 这样有不少空间没法给用户.
3 page-directory应当一次性分配, 而不要expand.

蛮有意思.

对了, Linux的malloc就是Kamp说的gnumalloc. 更常叫的是PTmalloc2(Wolfram Gloger), 或Doug Lea malloc.

[ 本帖最后由 Alligator27 于 2006-3-31 10:25 编辑 ]

雨丝风片

原帖由 Alligator27 于 2006-3-29 12:36 发表
PHK malloc 做得不错, 但有几点不好, 让我有点意外.
1 page-directory的大小是根据brk的值确定, 象LZ的测试程序是1MB的内存块, 与同样总内存但是1KB的内存块要分配同样大小的page-directory, 有点浪费.

page directory的大小确实是根据brk的内存大小来确定的，不知道你所说的浪费是指什么？page directry是用来管理malloc内部4K大小的page的，因此每个page都会对应一个条目。但page仅仅是malloc和内核的交易单位，在malloc内部，对于page的使用则有批发和零售两种。所谓批发就是按page的整数倍提供给malloc的用户使用，对于这些page，malloc只会为其分配一个page directory中的条目，再无其它。所谓零售，则是指那些大小为16、32、64、128、256、512、1024、2048的内存块，为了向用户提供这些类型的内存块，malloc就需要把自己管理的page打碎使用，一个page只能按一种规格打碎。对于每一个被打碎了的页面，malloc需要另外为其（在heap上）分配一个pginfo结构体，用于记录这个page的碎片规格、碎片总数、空闲碎片总数，以及用于快速定位空闲碎片的比特掩码等信息。实际上，page directory里面存放的就是指向pginfo结构体的指针，再由pginfo结构体指向实际的page。只是对于那些未被打碎的page来说，由于没有pginfo结构体，因此directory里面的对应条目就用来存放一些标识该page属性的标志了。

原帖由 Alligator27 于 2006-3-29 12:36 发表
2 brk() 失败后, 没有用mmap. 这样有不少空间没法给用户.

关于这一点，我觉得谈不上好不好，只是系统设计遵循的原则不同而已。有的系统的想法是不管是米饭还是馒头，能吃饱就行，哪儿那么骄气！而有的系统则尊重用户的知情权，米饭不够就多做点米饭，馒头不够就多做点馒头。一个人的主食种类和饭量一般都是固定的，很少会突然哪一天就想多吃一斤米饭的，因此买卖双方很容易就达成默契了。

原帖由 Alligator27 于 2006-3-29 12:36 发表
3 page-directory应当一次性分配, 而不要expand.

page directory确实可以一次性分配，现有方案以两个page为单位来扩展directory，其实也包含了一种“预分配”的概念在里面，只是没有一次性分配“预”得那么夸张而已。这个问题各有利弊，不好一概而论。不知道库函数里面有没有这种一次性抢占地盘的先例？

雨丝风片

我和congli将malloc的源代码剥离出来，通过修改，加入调试信息，构建了一个克隆版本的malloc。在此基础上进行了两次实验，得到了一些结果。

1、可以确定，把数据段上限调整到2934M左右的地方出现的malloc所得内存反而下降的原因就是因为通过mmap扩展page目录失败。出错代码位置为：

1. _____________________________________________________________________FreeBSD6.0
   
2. 384      /* Get new pages */
   
3. 385      new = (struct pginfo**) MMAP(i * malloc_pagesize);
   
4. 386      if (new == MAP_FAILED)
   
5. 387          return (0);
   
6. ______________________________________________/usr/src/lib/libc/stdlib/malloc.c

复制代码

2、两次实验的数据段分别设置为2934M和2935M，而两次的起始mmap位置分别为0xbf767000和0xbf867000，相差1M，证实了数据段对mmap生存空间的压缩。0xbf767000距内核空间只有8M，0xbf867000距内核空间就只有7M了，随着数据段的进一步增长，这个空间还会进一步压缩。注意，在这只有几M的空间中还有另外一个重要角色，stack。因此，mmap实际可用的空间还会更少。

3、malloc对page目录的扩展是以2个page，也即8192字节为单位进行的。扩展过程为先分配好新的page目录的空间，然后把旧的page目录的内容拷贝过去，最后再把旧的page目录释放掉。还有一点，mmap寻找空闲空间的算法是从低地址开始的first fit，这可以参考我写的关于FreeBSD虚存系统splay树的代码分析的文章。因此，只要“前面”空出了足以容纳新的page目录的空间，mmap就会杀个回马枪。因此，malloc扩展page目录时的mmap的内存使用模式大致如下图所示：

我们把mmap的每一轮同方向的增长称为一“级”。我们可以看到，除第一级稍有特殊情况之外，其余的级都是包含三次扩展，然后就会在“前方”出现可以容纳新的page目录的空间，于是mmap又从起始地址开始分配，开始新的一“级”。图中，每一条黑线的长度表示的就是malloc的page目录当前占有的内存空间。

同样，除了刚开始有一些例外之外，mmap对内存的最大要求，也即mmap“最远”到达的内存位置是由每一级的最后一次扩展的结束地址来定义的。如果内存有限，那么扩展失败就肯定出现在每一级的最后一次扩展上。如果把图画得更深一些，这个规律就会更明显。于是，我们想象有一跟纵向的“线”在图中左右移动，这根线就是mmap的生存空间的边界，它对page目录的扩展有没有什么规律？

我们以4096为一个单位来进行简单的推导，当然，还是需要忽略掉开头的情况。设第n级的第一根线的长度为B(n)，所有的B(n)构成一个等差数列，通项为B(n)=6n-3, (n>=2)。设第n级的最“远”内存需求，也即这一级最后一次扩展的结束地址为L(n)，显然这也是一个等差数列，通项为L(n)=18n-3, (n>=2)。

1M的空间相当于256个单位，我们关心的是上图中如果在横向缩短256个单位，会对图中的最长黑线长度产生什么影响？由于mmap的“右边”是stack，何时终止并不确定，因此我们就向左边对齐，用两次相差256个单位的边界来估计这种影响的大致数量。

首先假定右边界就是256个单位（此时的mmap空间为1M），即Ln=18n-3=256，得出n=14，即共可允许18级、54次扩展。此时的page目录空间为85个单位，348160字节，87040个条目。对应于heap上的87040个page，共340M。也就是说，如果mmap的生存空间为1M，malloc就可以在heap上分配340M的空间。

现在，我们把右边界向右移动256个单位（此时的mmap空间为2M），即Ln=18n-3=512，得出n=28，即此时共可允许28级、84次扩展。此时的page目录空间为169个单位，692224字节，173056个条目。对应于heap上的173056个page，共676M。

同样，当把右边界再次右移256个单位之后，页面目录对应的heap上的空间为1012M。。。

676 - 340 = 336，1012 - 676 = 336，也就是说，mmap空间每变动1M对heap空间的影响就是336M。这个336M正是前面的实验中发现的非常规则的线性关系中的递减步长。理论推导和实验结果完全一致。


关于上面推导过程的几点补充说明：

1、malloc对page目录的扩展是“搬家”式的。也就是说，当决定需要对page目录进行扩展的时候，就以新的尺寸、通过mmap系统调用、按first fit原则找到一块满足要求的区域，将旧的区域中的内容全部拷贝过去，然后再将旧的区域释放。

2、至于前面所给图中为何会出现规律性的“回头”现象，我们仍然按4096一个单位来描述。假设在某一级的开始，也就是从最左边的mmap的起始地址开始，这次的page目录记为A。之后进行扩展，按first fit原则找到的第一个满足要求的空闲空间就紧挨在A的后面，也就是B。我们把页面目录拷贝到B，同时将A的空间释放，显然，B要比A大两个单位。之后再次进行扩展，虽然前面有一个空闲空间A，但它并不“fit”，第一个fit的空闲空间位于B的后面，也即C，我们就把页面目录拷贝到C，同时将B释放，同样，C要比B大两个单位。另外，相邻的两个空闲空间A和B会被合并，记为AB。之后再次进行扩展，我们需要找到一个比C大两个单位的空间D，AB是遇到的第一个空间，但它是否“fit”呢？这可以转换成一个不等式问题。D等于a+6，AB等于2a+2，于是AB > D 也就成了2a+2 > a+6，解这个不等式，得a>4。

也就是说，只要最左边的那次（A）扩展后的page目录超过4个单位，那么在经历了B、C之后，AB合起来的空闲空间就肯定能够存放D。于是整幅图就呈现出了一种极有规律的“三步一回头”的景象。我们也正是基于这个事实才在上面的推导过程中提出了“级”的概念。

3、关于336的计算过程，需要对malloc的源代码有一定的了解。不过理解上面的推导不需太多的细节。此处是一个稍微详细一点的版本，以mmap空间为256个单位为例。首先通过公式Ln=18n-3=256算出n等于18，也就是说，256个单位的mmap空间总共可以允许18级扩展成功结束，其中每一级包括3次扩展，也就是总共54次扩展。显然，经过第54次扩展之后的page目录最大，有多大呢？注意，这个第54次扩展之后的page目录是第18级上的第三次扩展，而我们前面已经给出了每一级的第一次扩展的大小公式，即B(n)=6n-3。于是，我们可以求得第52次扩展之后的page目录的大小为B(18 )=81，而第54次比第52次大4个单位，于是第54次扩展之后的page目录的大小就是85个单位。一个4096的heap页面对应于page目录中的一个条目，一个条目是4个字节。所以，如果page目录此时占有85个单位，一个单位是4096字节，因此page目录就有85*4096=348160字节，那它就有348160/4=87040个条目，对应于87040个heap上的4K页面，共计356515840字节，即340M。

4、关于两个公式的推导，其中，B(2)＝9得自实验数据。

      B(n) = B(n-1) + 6                    (n>=3)
      B(2) = 9
推出  B(n) = 9 + (n - 2) * 6
           = 6n - 3                        (n>=2)

      L(n) = B(n) + B(n) + 2 + B(n) + 4
           = 18n - 3                       (n>=2)

[ 本帖最后由 雨丝风片 于 2007-4-21 10:25 编辑 ]

congli

惭愧
全是兄弟的努力,呵~~

雨丝风片

原帖由 congli 于 2006-3-30 15:49 发表
惭愧
全是兄弟的努力,呵~~

实验数据才是最宝贵的财富！

附上我们修改后的malloc.c和取得的2934、2935两组数据：

Alligator27

原帖由 雨丝风片 于 2006-3-30 15:24 发表

page directory的大小确实是根据brk的内存大小来确定的，不知道你所说的浪费是指什么？page directry是用来管理malloc内部4K大小的page的，因此每个page都会对应一个条目。但page仅仅是malloc和内核的交易单位， ...

Excellent work!  

让我解释一下我的意思.

1 如果把page directory看成一个array, 它的index是page number, 它的element是该page的管理信息(meta data). 如果用户程序的内存申请size远大于pagesize, 象LZ的测试程序是1MB的内存块, 那么page directory是sparse array. 所以我说有点浪费.

2 malloc不考虑mmap是不行的. 特别象FreeBSD, default heap的顶被mmap area固定了. 当brk到这个顶的时候, 用户不能再得到内存, 但mmap area还有很多空间. 这不是米饭/馒头的选择, 会饿死的. 换句话说, 不管kernel把mmap起始地址放哪儿, malloc都应当分配出~3GB给用户程序.

3 page-directory一次性分配只需要3MB (32bit), 而且只是virtual address. 完全值得. 第一, 只有一个sysem call. 第二, 不会有将来分配不到的可能. 第三, 因为不搬家,实际占用空间可能少一些.

雨丝风片

原帖由 Alligator27 于 2006-3-30 22:08 发表
1 如果把page directory看成一个array, 它的index是page number, 它的element是该page的管理信息(meta data). 如果用户程序的内存申请size远大于pagesize, 象LZ的测试程序是1MB的内存块, 那么page directory是sparse array. 所以我说有点浪费.

1、page目录中的条目和malloc管理的page之间有一一对应的关系，这和用户申请内存的大小是无关的。每个页面都要在这儿登个记，因此应该没有“稀疏”的问题。你的意思是不是说如果用户申请的内存是1M，相当于256个page，于是就需要256个page目录条目，而你认为其实只要找一个地方记录就可以了？我觉得这里还是要明确一下page目录的作用，它并不是用来记录所有分配给用户的内存的头指针的，它仅仅是用来记录malloc自身管理的每一个page的。你这次虽然是把256个页面作为一个整体交给了用户，但在用户将其释放之后，它们仍然处于malloc的管理之下，身份就变成了256个独立的空闲page。malloc就可以用它们来满足用户未来的各种分配需求，而且只要它们能满足，malloc就没有必要再去调用brk向系统要内存。基于上述意义，每一个page目录的条目都是“有用的”，因此不会有“稀疏”的问题。

原帖由 Alligator27 于 2006-3-30 22:08 发表
2 malloc不考虑mmap是不行的. 特别象FreeBSD, default heap的顶被mmap area固定了. 当brk到这个顶的时候, 用户不能再得到内存, 但mmap area还有很多空间. 这不是米饭/馒头的选择, 会饿死的. 换句话说, 不管kernel把mmap起始地址放哪儿, malloc都应当分配出~3GB给用户程序.

2、我觉得米饭馒头的比喻能够很好的说明这个问题。有的系统只管让顾客闭着眼睛吃饱，至于给你吃的是什么你别管。而有的系统则希望让顾客自己来选择，如果把米饭吃完了还没吃饱的话，要么你就把米饭多做一点，要么你就再吃两个馒头。回到内存话题，有的系统认为用户想要的就是内存，而对这块内存是从哪儿来的并不关心，于是在有些情况下就会用mmap来冒充malloc。而有的系统则认为用户有权自己去安排自己的地址空间，他有权决定自己申请的内存是来自heap的还是来自mmap的。如果heap的空间不够，你可以调整heap的大小，你也可以安排你的程序使用mmap。有时候，只管吩咐、什么事都让别人做了确实很方便，但DIY的感觉也确实不错啊！

原帖由 Alligator27 于 2006-3-30 22:08 发表
3 page-directory一次性分配只需要3MB (32bit), 而且只是virtual address. 完全值得. 第一, 只有一个sysem call. 第二, 不会有将来分配不到的可能. 第三, 因为不搬家,实际占用空间可能少一些.

3、这一点确实值得考虑和尝试。page目录现在的空间浪费确实就是因为搬家引起的，否则我也没必要去推算mmap空间的1M会影响heap上的多少M了。我唯一的担心就是，库函数“兴不兴”这样抢地盘？

Alligator27

原帖由 雨丝风片 于 2006-3-31 08:54 发表

1、page目录中的条目和malloc管理的page之间有一一对应的关系，这和用户申请内存的大小是无关的。每个页面都要在这儿登个记，因此应该没有“稀疏”的问题。你的意思是不是说如果用户申请的内存是1M，相当于256个 ...

我们是从不同的角度看这个问题.

1 同意. PHK的用意是page mapping. 我想说的是, 它是作的最坏打算, 既用户的粒度是page. 如果用户使用大内存块, 它就有浪费, 虽然不多, 因为一个用户块实际上只需要一条目录. 不过使用mapping的malloc都是这样, 无可厚非. 只是在你的测试中显示出这个问题.

2 用户是不用关心内存是从main heap, 还是从mmap里来的, 这点我完全同意. 但用户一定想用尽量多的内存, 不管从哪儿来, 怎么来, 我只要不断malloc, 它就应当给我3GB. 这是PHK最大的缺点. 我想这也是该帖的主题.

3. 库函数可不可以抢地盘. 看你问谁了. 有些用户可能会panic. 因为"hello world"的memory footprint 就有3MB. 但不会有什么实际影响的.