1. 內(nèi)存管理功能問(wèn)題

由于C++語(yǔ)言對(duì)內(nèi)存有主動(dòng)控制權(quán)，內(nèi)存使用靈活和效率高，但代價(jià)是不小心使用就會(huì)導(dǎo)致以下內(nèi)存錯(cuò)誤：

? memory overrun：寫內(nèi)存越界 ? double free：同一塊內(nèi)存釋放兩次 ? use after free：內(nèi)存釋放后使用 ? wild free：釋放內(nèi)存的參數(shù)為非法值 ? access uninitialized memory：訪問(wèn)未初始化內(nèi)存 ? read invalid memory：讀取非法內(nèi)存，本質(zhì)上也屬于內(nèi)存越界 ? memory leak：內(nèi)存泄露 ? use after return：caller訪問(wèn)一個(gè)指針，該指針指向callee的棧內(nèi)內(nèi)存 ? stack overflow：棧溢出

常用的解決內(nèi)存錯(cuò)誤的方法

• 代碼靜態(tài)檢測(cè)

靜態(tài)代碼檢測(cè)是指無(wú)需運(yùn)行被測(cè)代碼，通過(guò)詞法分析、語(yǔ)法分析、控制流、數(shù)據(jù)流分析等技術(shù)對(duì)程序代碼進(jìn)行掃描，找出代碼隱藏的錯(cuò)誤和缺陷，如參數(shù)不匹配，有歧義的嵌套語(yǔ)句，錯(cuò)誤的遞歸，非法計(jì)算，可能出現(xiàn)的空指針引用等等。統(tǒng)計(jì)證明，在整個(gè)軟件開發(fā)生命周期中，30%至70%的代碼邏輯設(shè)計(jì)和編碼缺陷是可以通過(guò)靜態(tài)代碼分析來(lái)發(fā)現(xiàn)和修復(fù)的。在C++項(xiàng)目開發(fā)過(guò)程中，因?yàn)槠錇榫幾g執(zhí)行語(yǔ)言，語(yǔ)言規(guī)則要求較高，開發(fā)團(tuán)隊(duì)往往要花費(fèi)大量的時(shí)間和精力發(fā)現(xiàn)并修改代碼缺陷。所以C++靜態(tài)代碼分析工具能夠幫助開發(fā)人員快速、有效的定位代碼缺陷并及時(shí)糾正這些問(wèn)題，從而極大地提高軟件可靠性并節(jié)省開發(fā)成本。

靜態(tài)代碼分析工具的優(yōu)勢(shì)：

1、自動(dòng)執(zhí)行靜態(tài)代碼分析，快速定位代碼隱藏錯(cuò)誤和缺陷。

2、幫助代碼設(shè)計(jì)人員更專注于分析和解決代碼設(shè)計(jì)缺陷。

3、減少在代碼人工檢查上花費(fèi)的時(shí)間，提高軟件可靠性并節(jié)省開發(fā)成本。

一些主流的靜態(tài)代碼檢測(cè)工具，免費(fèi)的cppcheck，clang static analyzer；

商用的coverity，pclint等

各個(gè)工具性能對(duì)比：

• 代碼動(dòng)態(tài)檢測(cè)

所謂的代碼動(dòng)態(tài)檢測(cè)，就是需要再程序運(yùn)行情況下，通過(guò)插入特殊指令，進(jìn)行動(dòng)態(tài)檢測(cè)和收集運(yùn)行數(shù)據(jù)信息，然后分析給出報(bào)告。

1.為了檢測(cè)內(nèi)存非法使用，需要hook內(nèi)存分配和操作函數(shù)。hook的方法可以是用C-preprocessor，也可以是在鏈接庫(kù)中直接定義（因?yàn)镚libc中的malloc/free等函數(shù)都是weak symbol），或是用LD_PRELOAD。另外，通過(guò)hook strcpy(),memmove()等函數(shù)可以檢測(cè)它們是否引起buffer overflow。

2. 為了檢查內(nèi)存的非法訪問(wèn)，需要對(duì)程序的內(nèi)存進(jìn)行bookkeeping，然后截獲每次訪存操作并檢測(cè)是否合法。bookkeeping的方法大同小異，主要思想是用shadow memory來(lái)驗(yàn)證某塊內(nèi)存的合法性。至于instrumentation的方法各種各樣。有run-time的，比如通過(guò)把程序運(yùn)行在虛擬機(jī)中或是通過(guò)binary translator來(lái)運(yùn)行；或是compile-time的，在編譯時(shí)就在訪存指令時(shí)就加入檢查操作。另外也可以通過(guò)在分配內(nèi)存前后加設(shè)為不可訪問(wèn)的guard page，這樣可以利用硬件(MMU)來(lái)觸發(fā)SIGSEGV，從而提高速度。

3.為了檢測(cè)棧的問(wèn)題，一般在stack上設(shè)置canary，即在函數(shù)調(diào)用時(shí)在棧上寫magic number或是隨機(jī)值，然后在函數(shù)返回時(shí)檢查是否被改寫。另外可以通過(guò)mprotect()在stack的頂端設(shè)置guard page，這樣棧溢出會(huì)導(dǎo)致SIGSEGV而不至于破壞數(shù)據(jù)。

工具總結(jié)對(duì)比，常用valgrind（檢測(cè)內(nèi)存泄露），gperftools（統(tǒng)計(jì)內(nèi)存消耗）等：

DBI：動(dòng)態(tài)二進(jìn)制工具 CTI：編譯時(shí)工具 UMR：未初始化的存儲(chǔ)器讀取 UAF：釋放后使用（又名懸掛指針） UAR：返回后使用 OOB：越界 x86：包括32和64-少量。在GCC 4.9中已刪除了 Mudflap，因?yàn)樗驯籄ddressSanitizer取代。 Guard Page：一系列內(nèi)存錯(cuò)誤檢測(cè)器（Linux上為電子圍欄或DUMA，Windows上為Page Heap，OS X上為 libgmalloc）gperftools：與TCMalloc捆綁在一起的各種性能工具/錯(cuò)誤檢測(cè)器。堆檢查器（檢漏器）僅在Linux上可用。調(diào)試分配器同時(shí)提供了保護(hù)頁(yè)和Canary值，以更精確地檢測(cè)OOB寫入，因此它比僅保護(hù)頁(yè)的檢測(cè)器要好。

2. C++內(nèi)存管理效率問(wèn)題

1、內(nèi)存管理可以分為三個(gè)層次

自底向上分別是：

• 第一層：操作系統(tǒng)內(nèi)核的內(nèi)存管理-虛擬內(nèi)存管理
• 第二層：glibc層維護(hù)的內(nèi)存管理算法
• 第三層：應(yīng)用程序從glibc動(dòng)態(tài)分配內(nèi)存后，根據(jù)應(yīng)用程序本身的程序特性進(jìn)行優(yōu)化， 比如SGI STL allocator，使用引用計(jì)數(shù)std::shared_ptr，RAII，實(shí)現(xiàn)應(yīng)用的內(nèi)存池等等。

當(dāng)然應(yīng)用程序也可以直接使用系統(tǒng)調(diào)用從內(nèi)核分配內(nèi)存，自己根據(jù)程序特性來(lái)維護(hù)內(nèi)存，但是會(huì)大大增加開發(fā)成本。

2、C++內(nèi)存管理問(wèn)題

• 頻繁的new/delete勢(shì)必會(huì)造成內(nèi)存碎片化，使內(nèi)存再分配和回收的效率下降；
• new/delete分配內(nèi)存在linux下默認(rèn)是通過(guò)調(diào)用glibc的api-malloc/free來(lái)實(shí)現(xiàn)的，而這些api是通過(guò)調(diào)用到linux的系統(tǒng)調(diào)用:

brk()/sbrk() // 通過(guò)移動(dòng)Heap堆頂指針brk，達(dá)到增加內(nèi)存目的 mmap()/munmap() // 通過(guò)文件影射的方式，把文件映射到mmap區(qū)

分配內(nèi)存 < DEFAULT_MMAP_THRESHOLD，走brk，從內(nèi)存池獲取，失敗的話走brk系統(tǒng)調(diào)用

分配內(nèi)存 > DEFAULT_MMAP_THRESHOLD，走mmap，直接調(diào)用mmap系統(tǒng)調(diào)用

其中，DEFAULT_MMAP_THRESHOLD默認(rèn)為128k，可通過(guò)mallopt進(jìn)行設(shè)置。

sbrk/brk系統(tǒng)調(diào)用的實(shí)現(xiàn)：分配內(nèi)存是通過(guò)調(diào)節(jié)堆頂?shù)奈恢脕?lái)實(shí)現(xiàn)， 堆頂?shù)奈恢檬峭ㄟ^(guò)函數(shù) brk 和 sbrk 進(jìn)行動(dòng)態(tài)調(diào)整，參考例子：

(1) 初始狀態(tài)：如圖 (1) 所示，系統(tǒng)已分配 ABCD 四塊內(nèi)存，其中 ABD 在堆內(nèi)分配， C 使用 mmap 分配。為簡(jiǎn)單起見，圖中忽略了如共享庫(kù)等文件映射區(qū)域的地址空間。

(2) E=malloc(100k) ：分配 100k 內(nèi)存，小于 128k ，從堆內(nèi)分配，堆內(nèi)剩余空間不足，擴(kuò)展堆頂 (brk) 指針。

(3) free(A) ：釋放 A 的內(nèi)存，在 glibc 中，僅僅是標(biāo)記為可用，形成一個(gè)內(nèi)存空洞 ( 碎片 )，并沒有真正釋放。如果此時(shí)需要分配 40k 以內(nèi)的空間，可重用此空間，剩余空間形成新的小碎片。

(4) free(C) ：C 空間大于 128K ，使用 mmap 分配，如果釋放 C ，會(huì)調(diào)用 munmap 系統(tǒng)調(diào)用來(lái)釋放，并會(huì)真正釋放該空間，還給 OS ，如圖 (4) 所示。

所以free的內(nèi)存不一定真正的歸還給OS，隨著系統(tǒng)頻繁地 malloc 和 free ，尤其對(duì)于小塊內(nèi)存，堆內(nèi)將產(chǎn)生越來(lái)越多不可用的碎片，導(dǎo)致“內(nèi)存泄露”。而這種“泄露”現(xiàn)象使用 valgrind 是無(wú)法檢測(cè)出來(lái)的。

• 綜上，頻繁內(nèi)存分配釋放還會(huì)導(dǎo)致大量系統(tǒng)調(diào)用開銷，影響效率，降低整體性能；

3. 常用解決上述問(wèn)題的方案

內(nèi)存池技術(shù)

內(nèi)存池方案通常一次從系統(tǒng)申請(qǐng)一大塊內(nèi)存塊，然后基于在這塊內(nèi)存塊可以進(jìn)行不同內(nèi)存策略實(shí)現(xiàn)，可以比較好得解決上面提到的問(wèn)題，一般采用內(nèi)存池有以下好處：

1.少量系統(tǒng)申請(qǐng)次數(shù)，非常少(幾沒有) 堆碎片。2.由于沒有系統(tǒng)調(diào)用等，比通常的內(nèi)存申請(qǐng)/釋放(比如通過(guò)malloc, new等)的方式快。3.可以檢查應(yīng)用的任何一塊內(nèi)存是否在內(nèi)存池里。4.寫一個(gè)”堆轉(zhuǎn)儲(chǔ)(Heap-Dump)”到你的硬盤(對(duì)事后的調(diào)試非常有用)。5.可以更方便實(shí)現(xiàn)某種內(nèi)存泄漏檢測(cè)(memory-leak detection)。

6.減少額外系統(tǒng)內(nèi)存管理開銷，可以節(jié)約內(nèi)存；

內(nèi)存管理方案實(shí)現(xiàn)的指標(biāo)：

• 額外的空間損耗盡量少
• 分配速度盡可能快
• 盡量避免內(nèi)存碎片
• 多線程性能好
• 緩存本地化友好
• 通用性，兼容性，可移植性，易調(diào)試等

各個(gè)內(nèi)存分配器的實(shí)現(xiàn)都是在以上的各種指標(biāo)中進(jìn)行權(quán)衡選擇.

4. 一些業(yè)界主流的內(nèi)存管理方案

SGI STL allocator

是比較優(yōu)秀的 C++庫(kù)內(nèi)存分配器(細(xì)節(jié)參考上面描述）

ptmalloc

是glibc的內(nèi)存分配管理模塊, 主要核心技術(shù)點(diǎn)：

1. Arena-main /thread；支持多線程
2. Heap segments；for thread arena via by mmap call ；提高管理
3. chunk/Top chunk/Last Remainder chunk；提高內(nèi)存分配的局部性
4. bins/fast bin/unsorted bin/small bin/large bin;提高分配效率

ptmalloc的缺陷

• 后分配的內(nèi)存先釋放,因?yàn)?ptmalloc 收縮內(nèi)存是從 top chunk 開始,如果與 top chunk 相鄰的 chunk 不能釋放, top chunk 以下的 chunk 都無(wú)法釋放。
• 多線程鎖開銷大， 需要避免多線程頻繁分配釋放。
• 內(nèi)存從thread的areana中分配， 內(nèi)存不能從一個(gè)arena移動(dòng)到另一個(gè)arena， 就是說(shuō)如果多線程使用內(nèi)存不均衡，容易導(dǎo)致內(nèi)存的浪費(fèi)。比如說(shuō)線程1使用了300M內(nèi)存，完成任務(wù)后glibc沒有釋放給操作系統(tǒng)，線程2開始創(chuàng)建了一個(gè)新的arena， 但是線程1的300M卻不能用了。
• 每個(gè)chunk至少8字節(jié)的開銷很大
• 不定期分配長(zhǎng)生命周期的內(nèi)存容易造成內(nèi)存碎片，不利于回收。64位系統(tǒng)最好分配32M以上內(nèi)存，這是使用mmap的閾值。

tcmalloc

google的gperftools內(nèi)存分配管理模塊, 主要核心技術(shù)點(diǎn)：

1. thread-localcache/periodic garbagecollections/CentralFreeList；提高多線程性能,提高cache利用率

TCMalloc給每個(gè)線程分配了一個(gè)線程局部緩存。小分配可以直接由線程局部緩存來(lái)滿足。需要的話，會(huì)將對(duì)象從中央數(shù)據(jù)結(jié)構(gòu)移動(dòng)到線程局部緩存中，同時(shí)定期的垃圾收集將用于把內(nèi)存從線程局部緩存遷移回中央數(shù)據(jù)結(jié)構(gòu)中：

2. Thread Specific Free List/size-classes [8,16,32,…32k]: 更好小對(duì)象內(nèi)存分配;

每個(gè)小對(duì)象的大小都會(huì)被映射到170個(gè)可分配的尺寸類別中的一個(gè)。例如，在分配961到1024字節(jié)時(shí)，都會(huì)歸整為1024字節(jié)。尺寸類別這樣隔開：較小的尺寸相差8字節(jié)，較大的尺寸相差16字節(jié)，再大一點(diǎn)的尺寸差32字節(jié)，如此類推。最大的間隔（對(duì)于尺寸 >= ~2K的）是256字節(jié)。一個(gè)線程緩存對(duì)每個(gè)尺寸類都包含了一個(gè)自由對(duì)象的單向鏈表

3. The central page heap：更好的大對(duì)象內(nèi)存分配，一個(gè)大對(duì)象的尺寸(> 32K)會(huì)被除以一個(gè)頁(yè)面尺寸（4K）并取整（大于結(jié)果的最小整數(shù)），同時(shí)是由中央頁(yè)面堆來(lái)處理 的。中央頁(yè)面堆又是一個(gè)自由列表的陣列。對(duì)于i < 256而言，第k個(gè)條目是一個(gè)由k個(gè)頁(yè)面組成的自由列表。第256個(gè)條目則是一個(gè)包含了長(zhǎng)度>= 256個(gè)頁(yè)面的自由列表：

4. Spans:

TCMalloc管理的堆由一系列頁(yè)面組成。連續(xù)的頁(yè)面由一個(gè)“跨度”（Span）對(duì)象來(lái)表示。一個(gè)跨度可以是_已被分配_或者是_自由_的。如果是自由的，跨度則會(huì)是一個(gè)頁(yè)面堆鏈表中的一個(gè)條目。如果已被分配，它會(huì)是一個(gè)已經(jīng)被傳遞給應(yīng)用程序的大對(duì)象，或者是一個(gè)已經(jīng)被分割成一系列小對(duì)象的一個(gè)頁(yè)面。如果是被分割成小對(duì)象的，對(duì)象的尺寸類別會(huì)被記錄在跨度中。

由頁(yè)面號(hào)索引的中央數(shù)組可以用于找到某個(gè)頁(yè)面所屬的跨度。例如，下面的跨度_a_占據(jù)了2個(gè)頁(yè)面，跨度_b_占據(jù)了1個(gè)頁(yè)面，跨度_c_占據(jù)了5個(gè)頁(yè)面最后跨度_d_占據(jù)了3個(gè)頁(yè)面。

tcmalloc的改進(jìn)

• ThreadCache會(huì)階段性的回收內(nèi)存到CentralCache里。解決了ptmalloc2中arena之間不能遷移的問(wèn)題。
• Tcmalloc占用更少的額外空間。例如，分配N個(gè)8字節(jié)對(duì)象可能要使用大約8N * 1.01字節(jié)的空間。即，多用百分之一的空間。Ptmalloc2使用最少8字節(jié)描述一個(gè)chunk。
• 更快。小對(duì)象幾乎無(wú)鎖， >32KB的對(duì)象從CentralCache中分配使用自旋鎖。并且>32KB對(duì)象都是頁(yè)面對(duì)齊分配，多線程的時(shí)候應(yīng)盡量避免頻繁分配，否則也會(huì)造成自旋鎖的競(jìng)爭(zhēng)和頁(yè)面對(duì)齊造成的浪費(fèi)。

jemalloc

FreeBSD的提供的內(nèi)存分配管理模塊, 主要核心技術(shù)點(diǎn)：

1. 與tcmalloc類似，每個(gè)線程同樣在<32KB的時(shí)候無(wú)鎖使用線程本地cache;
2. Jemalloc在64bits系統(tǒng)上使用下面的size-class分類：

Small: [8], [16, 32, 48, …, 128], [192, 256, 320, …, 512], [768, 1024, 1280, …, 3840] Large: [4 KiB, 8 KiB, 12 KiB, …, 4072 KiB] Huge: [4 MiB, 8 MiB, 12 MiB, …]

3. small/large對(duì)象查找metadata需要常量時(shí)間， huge對(duì)象通過(guò)全局紅黑樹在對(duì)數(shù)時(shí)間內(nèi)查找
4. 虛擬內(nèi)存被邏輯上分割成chunks（默認(rèn)是4MB，1024個(gè)4k頁(yè)），應(yīng)用線程通過(guò)round-robin算法在第一次malloc的時(shí)候分配arena， 每個(gè)arena都是相互獨(dú)立的，維護(hù)自己的chunks， chunk切割pages到small/large對(duì)象。free()的內(nèi)存總是返回到所屬的arena中，而不管是哪個(gè)線程調(diào)用free().

上圖可以看到每個(gè)arena管理的arena chunk結(jié)構(gòu)， 開始的header主要是維護(hù)了一個(gè)page map（1024個(gè)頁(yè)面關(guān)聯(lián)的對(duì)象狀態(tài)）， header下方就是它的頁(yè)面空間。Small對(duì)象被分到一起， metadata信息存放在起始位置。large chunk相互獨(dú)立，它的metadata信息存放在chunk header map中。

5. 通過(guò)arena分配的時(shí)候需要對(duì)arena bin（每個(gè)small size-class一個(gè)，細(xì)粒度）加鎖，或arena本身加鎖。并且線程cache對(duì)象也會(huì)通過(guò)垃圾回收指數(shù)退讓算法返回到arena中。

jemalloc的優(yōu)化

• Jmalloc小對(duì)象也根據(jù)size-class，但是它使用了低地址優(yōu)先的策略，來(lái)降低內(nèi)存碎片化。
• Jemalloc大概需要2%的額外開銷。（tcmalloc 1%， ptmalloc最少8B）.
• Jemalloc和tcmalloc類似的線程本地緩存，避免鎖的競(jìng)爭(zhēng) .
• 相對(duì)未使用的頁(yè)面，優(yōu)先使用dirty page，提升緩存命中。

性能比較

測(cè)試環(huán)境：2x Intel E5/2.2Ghz with 8 real cores per socket，16 real cores， 開啟hyper-threading， 總共32個(gè)vcpu。16個(gè)table，每個(gè)5M row。OLTP_RO測(cè)試包含5個(gè)select查詢：select_ranges, select_order_ranges, select_distinct_ranges, select_sum_ranges：

facebook的測(cè)試結(jié)果:

服務(wù)器吞吐量分別用6個(gè)malloc實(shí)現(xiàn)的對(duì)比數(shù)據(jù)，可以看到tcmalloc和jemalloc最好(tcmalloc這里版本較舊)。

總結(jié)

可以看出tcmalloc和jemalloc性能接近，比ptmalloc性能要好，在多線程環(huán)境使用tcmalloc和jemalloc效果非常明顯。一般支持多核多線程擴(kuò)展情況下可以使用jemalloc；反之使用tcmalloc可能是更好的選擇。