删帖吧

xyfree

滚

OwnWaterloo

回复 11# xyfree

>> 用户有可能自己映射文件到地址空间，这样没法对内存段做任何保证。
这个没看明白……
用户映射的区域你也要负责管理么？

如果不考虑这个， 很容易满足的哦。

先说第3个条件。
其实就是内存管理仅仅包含管理功能，不包含诊断功能。就像free一样， 必须是由malloc得来的， 否则用户自己负责。
如果真需要其他功能， 可以在这之上完成。

再说第2个条件：VirtualAlloc(以及CreateFileMapping)与mmap分配的大小都是有粒度的。
第1个条件： VirtualAlloc(以及CreateFileMapping)分配的起始地址也是在一个边界上的。
mmap我不太确定……   ieee1003说得比较隐晦……
但linux+glibc是在页边界上的。

比如tcmalloc吧， 从VirtualAlloc/mmap（sbrk似乎是它自己强制分配在页边界上）得到满足上面条件的内存。
之后从某个地址查询所在内存段就通过一个很大的array，直接取模得到index。

我记得你代码也是这么做的吧？ 怎么又怀疑起来了……

xyfree

滚

zylthinking

回复  OwnWaterloo


    问题就是在于mmap 之类的东西，你不能假设整个地址空间都归你管理……
    所 ...
xyfree 发表于 2011-09-28 18:14

这是个啥东西？ 似乎挺有意思的说

zylthinking

回复  OwnWaterloo

可以把整个地址空间，在逻辑上（而不是实际分配）划分成相等大小的片区。

然后哪些片区上存在内存段，就注册一下，使之与这个片区关联
xyfree 发表于 2011-09-28 18:14

是不是保存某片区中存在几个内存段的信息保存下来更合适些？
类似与桶。

先根据地址找片区， 找到了就在里面比较内存段地址

OwnWaterloo

回复 13# xyfree

>>    问题就是在于mmap 之类的东西，你不能假设整个地址空间都归你管理……
>>    所以只要存在其他可能影响内存空间分布的东西，你就无法保证内存块的地址一定符合条件。

先说 VirtualAlloc。 妈逼VirtualAlloc又两个粒度……  这里只说提交粒度。。。

不管用户如何用 VirtualAlloc/CreateFileMapping或者其他更高层的分配接口。
但只要你是用 VirtualAlloc 获得的内存， 那肯定是在页边界上的， 大小肯定是页的整数倍。
总共就2^32/2^12=2^20个页（且按4G算，实际只有2-3G）。
用一个1M元素的指针数组管理就完了……
比如你从 VirtualAlloc 得到了 [x*2^12, x*2^12+4k)， 就把管理这4k内存的数据的地址放到那个数组的 x 项里……
如果是 [y*2^12, y*2^12+8k) 那就把管理这8k内存的数据的地址放到 y, y+1 项目里……
查询时直接右移12位得到index……
用户不是通过你的接口分配的话， 对应的元素就等它空着……
tcmalloc 一启动就占用4M地址空间就是这么来的……

而mmap， 它是个规范， 而且对起始地址的边界说得很含糊……
但说到具体实现， 比如linux+glibc经过测试就是在页边界的， 也可以这么搞……

虽然很占内存， 但这是最快（常数时间）的方法了……

OwnWaterloo

回复 13# xyfree

关于二分…… 最多32/64次比较就能得知：
1. p 是否归你管理
2. 如果是， 对应的数据是什么
难道不是这样么？

xyfree

滚

OwnWaterloo

回复 18# xyfree

1. 边界 [x*B-y,x*B+a) (y<B)
如果起始地址不是B的整数倍， [x*B-y,x*B) 之间的p/B就不是该块独占。
[(x-1)*B,x*B-y) 之间的p/B会得到相同的结果。

2. 大小
大小也是同样，尾部可能会与其他块首部重叠。

如果小心处理这些问题应该可以。

因为我最初目的是要分配可执行的内存， 所以malloc作为底层分配是不行的。
只能VirtualAlloc/mmap干活， 针对它们来实现， 可能无意中增加了不需要的限制条件……

zhanglistar

整个地址空间中存在若干互不重叠的区间，要查找某个地址在哪个区间。
有什么好的思路或者算法？

------ ...
xyfree 发表于 2011-09-28 00:02

    对于第一个问题，提供个思路，使用二叉查找树，avl或者rb tree，都可以。