寫這個的也是面試官的一道題, 問 python 中內(nèi)存是怎么分配的, 其實這個問題是一個很復雜的問題, 因為涉及到好多個層次, 分別包括:
Python 對象內(nèi)部的內(nèi)存管理
Python 虛擬機的內(nèi)存管理 (memory allocator)
malloc 內(nèi)存管理
linux 的內(nèi)存管理
這次就從機制上, 用代碼, 介紹一下這幾層內(nèi)存管理的大致實現(xiàn).
閱讀的過程中, 可以重點關(guān)注單獨自己層要解決的和其它層不一樣的問題和他與其他層的相似之處.
Python 內(nèi)部對象的內(nèi)存管理
這里能說的比較少, 每個對象的面臨的場景不一樣, 簡單來說, 比如 Python 的 List, list 每次發(fā)現(xiàn)容量滿了的時候, 都會預先申請一些空間, 我們在 Objects/listobject.c 中 的 repr 方法里查看一下 list 的狀態(tài)
這樣 每次打印的時候 就能看的 list 狀態(tài)
試一下
可以看到 只插了一個元素 卻申請了 4 個元素空間
在插了到了 5 個元素空間變成了 8
其實其他的對象也有類似的機制, 會提前申請大一些的內(nèi)存, 用來插入. 這樣的目的也是減少從下級的內(nèi)存分配器申請內(nèi)存
那我們申請內(nèi)存的下一級在哪里呢?
我們看 listobject.c 的代碼
我們看到
大致猜想一下, PyObject_GC_New 這個應該就是下一層的內(nèi)存分配器的接口, _PyObject_GC_TRACK 這個應該是處理垃圾回收的 暫時不管
Python 虛擬機的內(nèi)存管理 (memory allocator)
不斷的緊跟函數(shù)調(diào)用關(guān)系 在Objects/obmalloc.c 中 我們發(fā)現(xiàn)了
這個, 這個應該是 python 垃圾分配器的接口, 看了一堆麻煩的調(diào)用關(guān)系以后,
我們 找到了這個接口的實現(xiàn), 首先他也是分層的, 分為 raw 和 mem, obj 三層, 由于 mem,obj用的一個分配器, 我們把它當做一個來看, 去看一下 PYMALLOC_ALLOC的實現(xiàn)
可以看到
紅線一組目測就是我們要的東西
點開發(fā)現(xiàn) 同樣的思想又來了, 先看看能不能申請成功不能就去下一層, python 虛擬機里這個限制是 512Byte, 下一層就是我們的剛剛看到的 raw_alloc 跟一下看到了
熟悉的 malloc 這里就不管了, 我們把重點放在 pymalloc_alloc 這個上面.
簡單看一下邏輯, 大約意思是, 我們先從一個已經(jīng)用過的 usedpool 池子里找, 沒有了就從 allocate_from_new_pool , 最后返回一個 blocks數(shù)組, 代表申請的空間.
好, 從這里起, 我們就看到了 python 內(nèi)存分配的核心, pool 和 block, 我們拋棄掉流程上的東西, 從 block pool , uesedpool 是什么開始研究,
內(nèi)存塊的申請和釋放
點開定義
首先 block 就很簡單了 就是一個 unit_8 表示一個字節(jié)的控件, pool 一眼就看出來這是一個雙向鏈表,pool_head是鏈表的頭指針
再看一下 used_pool
這個定義不是人能看懂的, 大約意思就是有一堆大小不同的 pool 每個倆個存起來, 我們運行起來打個斷點看看, 每次調(diào)用這個都會不斷,遇到空的,都會調(diào)用allocate_from_new_pool的初始化, 結(jié)合一些資料, 我們大約知道這個是一堆大小不同的 pool 連起來, 每一個上的szidx 是提供的 block數(shù)組 的大小, 用一半是為了快速根據(jù)大小定位到下標(不太懂)
我們把多個 block 組合在一起叫做內(nèi)存塊, pool 分配按照大小不同的內(nèi)存塊來分配
初始化的過程 代碼位于?https://github.com/python/cpython/blob/master/Objects/obmalloc.c#L1549?前面的申請pool過程暫時不表,重點是后面的步驟,很明確感覺是一個頭插法, 不停地插入到 usedpools 所對應大小的頭部:
初始化了一些字段:
首先用 index2size 算出下標對應的塊大小
bp 應該是頭部的大小 一個pool 4k 減去頭部就是塊的大小
nextoffset 是還沒用過空間的 offset
maxnextooffset 應該是最大的空間
freeblock 就是指向首個空閑的, 然后這個空閑的內(nèi)存塊指向了 NULL, 這里應該是這樣一個結(jié)構(gòu)
熟悉 stl 的sgi_alloc的同學知道, 有一種優(yōu)化內(nèi)存分配器鏈表占用空間的手段的方法, 就是把塊空的時候的值設(shè)置成下一個節(jié)點的地址, 這樣既可以拉倆表, 有省去了一個指針的空間
初始化后的usedpool 大約如下圖所示
可以參考這個圖的結(jié)構(gòu):
好, 知道這些了我們看看怎么用的,
我們看到大約就是 增加一下使用的 內(nèi)存塊, 把內(nèi)存塊從倆表摘出來, 如果內(nèi)存塊是末節(jié)點, 就拓展, 如果不是末節(jié)點, 就說明這里正好是一個空閑的塊, 那么直接把這個拿出來, 讓 freeblock 指向他的下一個節(jié)點就好 (頭部刪除). 目測這里的拓展就是把尾巴的那一個大塊切出來分成小塊.
拓展的邏輯, 就是從尾巴拿空間, 扣除一個塊
大約就是這么一個轉(zhuǎn)換, 如果尾巴拿不出來了, 那說明這個 pool已經(jīng)滿了, 就把整個 pool 刪除.
注解 這里我們就看懂了 從 pool 拿一個 block 的所有過程, 總體上來看 是一個對 以freeblock 為倆表頭結(jié)點的 next 指針的一條鏈表,進行頭部操作, 從頭部刪除結(jié)點并且把剩余的插入到頭部, 以此來達到高效操作,?
看完了這里, 我們基本搞懂了申請一個內(nèi)存塊的邏輯, 那么歸還一個內(nèi)存塊的邏輯就是自然而然了
我們打開 pymalloc_alloc_free 函數(shù)?https://github.com/python/cpython/blob/master/Objects/obmalloc.c#L1860:
一看, 涉及到的邏輯簡直不要太簡單, 核心邏輯就是一個頭插法, 先通過內(nèi)存大小 + 偏移量, 算出pool_head 的位置(好騷啊), 然后進 pool 頭插一梭子, 就完事了
到此位置, 我們對于 pool 的 內(nèi)存塊的申請和釋放已經(jīng)了如指掌了, 不過, 還有幾多烏云沒有解開, 那就是?https://github.com/python/cpython/blob/master/Objects/obmalloc.c#L1459?前面那坨邏輯 和 pymalloc_free 的 insert_too_freepool 的邏輯, 接下來就輪到 arena 出場了
pool的牧羊人 arena
首先我們看一下 arena 的定義
又是一個眼熟的雙鏈表, 內(nèi)存分配器真的很喜歡這個數(shù)據(jù)結(jié)構(gòu), 里面簡單看了一下, 主要是管理 pool 的信息, 一個是 pool 的鏈表首節(jié)點, 一個是數(shù)量, 數(shù)量包括, 可以用的 (nfreepools) 和總共的(ntotalpool), 一減就是不可以用的了
我們再次返回 allocate_from_new_pool 中,
這個代碼比較長, 大約可以分為 3 部分:
如果當前沒有可用的 arenas 去申請一個, usable_arenas是一個全局變量
維護nfp2lasta 就是一個用來快速找到滿足數(shù)量的 freepool 最少的 freepool 的表
拉出來 pool, 作為內(nèi)存塊
我們先看看一個 arena 怎么創(chuàng)建的吧, 就是new_arena, 去看看這個函數(shù)做了什么
這部分可以分成三個大塊, 分別是 :
已經(jīng)沒有不可用 arena 時 申請新的(arena)
不可用的arena (ununsed_arena_object) 的第一個摘出來, 并且初始化, 值得一提的是, 他freeppools 初始化成了 NULL,pool_address是指向了arena 代表的頭部
我們在看看 allocate_from_new_pool 是怎么使用 pool 的,
首先讓 pool 等于 freepools, 然后做了個判斷, 這里我們先不討論 freepools 不為空的情況, 這個應該和釋放的邏輯有關(guān). 我們看為空的情況
簡單的一看, 就是一個從頭部截取一塊內(nèi)存(POOL_SIZE 4KB)當做鏈表的一項. 檢查這個 arena 的剩余的 pool 得數(shù)量, 沒了就從可用鏈表中刪除.
到這里為止, 我們看懂了從一個初始化好的 arena 拿走一個 pool 的過程:?
1. 新的 arena 申請好了會放在usable_arena 中 2. 從 usable_arena中的 pool_address 形成的鏈表中拿出來一個 pool, 拿完了發(fā)現(xiàn)沒剩余的了就刪除他
理解了拿去, 我們開始看 unused_arena_object 和 free_pool 是怎么在 pool 歸還中發(fā)揮作用
接下來 我們看 pymalloc_free 的 insert_too_freepool ,
這個函數(shù)分成倆部分, 開頭的邏輯是一個通用的歸還. 下面的邏輯是根據(jù)不同的情況做不同的處理, 歸還的邏輯比較簡單, 先把鏈表放回去, 讓 freepool 指向了歸還的這個 pool, 這里沒有做節(jié)約內(nèi)存, 直接用的 pool 的指針, 然后找到這個鏈表的 arena 從一個 全局變量arenas 目測是所有的 arenas, 該增減增加. 問題是之后的分情況討論
他這個注釋寫的也比較清楚, 我們就跟著注釋看源碼:
case1 :如果所有的pool歸還了 就 free 掉:
總共三步, 1.usale 刪除這個節(jié)點, 2. arena結(jié)構(gòu)體放入unsable 里 3. 釋放所有內(nèi)存
case2: 只歸還一個 pool
只歸還一個 pool 就把它放入 usable_arenas 的頭部, 底下處理一下查找表
case3: case3 是一個子步驟, 每次插入完了都檢查一下順序 讓 空閑 pool 數(shù)量少的 arena 放在前面, 這里就不貼代碼了可以看?https://github.com/python/cpython/blob/master/Objects/obmalloc.c#L1825?這里
綜上所述 , 我們心中可以有這么一個結(jié)構(gòu):
每個 arena 放著一堆 pool,
全局 arenas 放著所有 arena
usable_arenas_object 放著可以用的 arenas 指的一個分配好pool 的 arena, 按著空閑的 pool 的數(shù)量排序的一個單鏈表
unusable_arena_object 放著 沒有分配好 pool 的 arena, 一般是釋放了所有使用過的 pool 得 arena, 會把結(jié)構(gòu)放在這里
arena 的 pool_address 是一個未被使用過的鏈表的頭, freepool 是歸還回來的 pool 的鏈表
再看一下之前未解決的 allocate_from_new_pool 的 freepool 不為空的情況:
直觀感受就是一個頭部刪除....沒什么可說的了
總結(jié)
至此, 我們理解完 python 虛擬機的內(nèi)存管理的流程了, 首先 利用這套機制的內(nèi)存申請大小在 SMALL_REQUEST_THRESHOLD 限制 (這個是 512 byte), 大于這個會直接使用 malloc 申請.
然后我們申請的單位是內(nèi)存塊 由多個 block(1byte) 組成, 申請 block 向 pool 申請, 一個 pool 大小 為 POOL_SIZE , 默認 4kb 和系統(tǒng)頁大小一致, pool 的內(nèi)存就是內(nèi)存塊的內(nèi)存, pool 里的內(nèi)存塊用一種壓縮的鏈表的方式連接在一起.并且用 used_pool 作為一個緩存. 可以直接拿到 可以用的pool.
pool 不夠了要向 arena 申請, arena 是一個管理 pool 的東西, 他一塊里有未使用過的 pool和 已經(jīng)歸還的 pool 得信息, 優(yōu)先會使用 usable_arena_object鏈表上的 arena 里拿 pool, 這個按照剩余可用的 pool 升序排列, 沒有了會從 unusable_arena_object 拿 arena 分配內(nèi)存構(gòu)建 arena 放入 usable_arena
釋放內(nèi)存也是先釋放 block, 用頭插法插入 pool 中, 如果一個 pool 全部釋放了, 就放回 arena里, 如果一個 arena 里所有的 pool 都釋放了, 就放回 unuable_pool_object, 否則根據(jù)剩余的pool 數(shù)量, 提升自己在 unabel_pool_object的位置.
最后我們可以用
來查看 python 虛擬機這層內(nèi)存分配的一些狀態(tài)信息
下一篇會分析 malloc 的實現(xiàn), 馬上就要看到一種濃濃的我好像在哪里見過的感覺了哈哈哈
參考資料
