刪帖吧

xyfree

滾

OwnWaterloo

回復(fù) 11# xyfree

>> 用戶有可能自己映射文件到地址空間，這樣沒(méi)法對(duì)內(nèi)存段做任何保證。
這個(gè)沒(méi)看明白……
用戶映射的區(qū)域你也要負(fù)責(zé)管理么？

如果不考慮這個(gè)， 很容易滿足的哦。

先說(shuō)第3個(gè)條件。
其實(shí)就是內(nèi)存管理僅僅包含管理功能，不包含診斷功能。就像free一樣， 必須是由malloc得來(lái)的， 否則用戶自己負(fù)責(zé)。
如果真需要其他功能， 可以在這之上完成。

再說(shuō)第2個(gè)條件：VirtualAlloc(以及CreateFileMapping)與mmap分配的大小都是有粒度的。
第1個(gè)條件： VirtualAlloc(以及CreateFileMapping)分配的起始地址也是在一個(gè)邊界上的。
mmap我不太確定……   ieee1003說(shuō)得比較隱晦……
但linux+glibc是在頁(yè)邊界上的。

比如tcmalloc吧， 從VirtualAlloc/mmap（sbrk似乎是它自己強(qiáng)制分配在頁(yè)邊界上）得到滿足上面條件的內(nèi)存。
之后從某個(gè)地址查詢所在內(nèi)存段就通過(guò)一個(gè)很大的array，直接取模得到index。

我記得你代碼也是這么做的吧？ 怎么又懷疑起來(lái)了……

xyfree

滾

zylthinking

回復(fù)  OwnWaterloo


    問(wèn)題就是在于mmap 之類的東西，你不能假設(shè)整個(gè)地址空間都?xì)w你管理……
    所 ...
xyfree 發(fā)表于 2011-09-28 18:14

這是個(gè)啥東西？ 似乎挺有意思的說(shuō)

zylthinking

回復(fù)  OwnWaterloo

可以把整個(gè)地址空間，在邏輯上（而不是實(shí)際分配）劃分成相等大小的片區(qū)。

然后哪些片區(qū)上存在內(nèi)存段，就注冊(cè)一下，使之與這個(gè)片區(qū)關(guān)聯(lián)
xyfree 發(fā)表于 2011-09-28 18:14

是不是保存某片區(qū)中存在幾個(gè)內(nèi)存段的信息保存下來(lái)更合適些？
類似與桶。

先根據(jù)地址找片區(qū)， 找到了就在里面比較內(nèi)存段地址

OwnWaterloo

回復(fù) 13# xyfree

>>    問(wèn)題就是在于mmap 之類的東西，你不能假設(shè)整個(gè)地址空間都?xì)w你管理……
>>    所以只要存在其他可能影響內(nèi)存空間分布的東西，你就無(wú)法保證內(nèi)存塊的地址一定符合條件。

先說(shuō) VirtualAlloc。 媽逼VirtualAlloc又兩個(gè)粒度……  這里只說(shuō)提交粒度。。。

不管用戶如何用 VirtualAlloc/CreateFileMapping或者其他更高層的分配接口。
但只要你是用 VirtualAlloc 獲得的內(nèi)存， 那肯定是在頁(yè)邊界上的， 大小肯定是頁(yè)的整數(shù)倍。
總共就2^32/2^12=2^20個(gè)頁(yè)（且按4G算，實(shí)際只有2-3G）。
用一個(gè)1M元素的指針數(shù)組管理就完了……
比如你從 VirtualAlloc 得到了 [x*2^12, x*2^12+4k)， 就把管理這4k內(nèi)存的數(shù)據(jù)的地址放到那個(gè)數(shù)組的 x 項(xiàng)里……
如果是 [y*2^12, y*2^12+8k) 那就把管理這8k內(nèi)存的數(shù)據(jù)的地址放到 y, y+1 項(xiàng)目里……
查詢時(shí)直接右移12位得到index……
用戶不是通過(guò)你的接口分配的話， 對(duì)應(yīng)的元素就等它空著……
tcmalloc 一啟動(dòng)就占用4M地址空間就是這么來(lái)的……

而mmap， 它是個(gè)規(guī)范， 而且對(duì)起始地址的邊界說(shuō)得很含糊……
但說(shuō)到具體實(shí)現(xiàn)， 比如linux+glibc經(jīng)過(guò)測(cè)試就是在頁(yè)邊界的， 也可以這么搞……

雖然很占內(nèi)存， 但這是最快（常數(shù)時(shí)間）的方法了……

OwnWaterloo

回復(fù) 13# xyfree

關(guān)于二分…… 最多32/64次比較就能得知：
1. p 是否歸你管理
2. 如果是， 對(duì)應(yīng)的數(shù)據(jù)是什么
難道不是這樣么？

xyfree

滾

OwnWaterloo

回復(fù) 18# xyfree

1. 邊界 [x*B-y,x*B+a) (y<B)
如果起始地址不是B的整數(shù)倍， [x*B-y,x*B) 之間的p/B就不是該塊獨(dú)占。
[(x-1)*B,x*B-y) 之間的p/B會(huì)得到相同的結(jié)果。

2. 大小
大小也是同樣，尾部可能會(huì)與其他塊首部重疊。

如果小心處理這些問(wèn)題應(yīng)該可以。

因?yàn)槲易畛跄康氖且�分配可�?zhí)行的內(nèi)存， 所以malloc作為底層分配是不行的。
只能VirtualAlloc/mmap干活， 針對(duì)它們來(lái)實(shí)現(xiàn)， 可能無(wú)意中增加了不需要的限制條件……

zhanglistar

整個(gè)地址空間中存在若干互不重疊的區(qū)間，要查找某個(gè)地址在哪個(gè)區(qū)間。
有什么好的思路或者算法？

------ ...
xyfree 發(fā)表于 2011-09-28 00:02

    對(duì)于第一個(gè)問(wèn)題，提供個(gè)思路，使用二叉查找樹(shù)，avl或者rb tree，都可以。