Edison.X. Blog

這裡是 part (II) ，欲看 part (I) 與相關目錄 請至此。本篇主題主要圍繞在 (8. dbg_malloc / 9. alignment allocate memory)，鑑於時間有限，這兩篇文章所提之方法並沒全以 coding 示之，唯以簡易方式進行，筆者會於文章再探討這些技巧被探討之議題。

初學者面試想不到 topic，我覺得帶這兩個作品過去應該不錯，但要花一點時間完成。

8. dbg_malloc

9. alignment allocate memory

A. others

B. Q & A

C. Reference

8. dbg_malloc (2013.1.15 更新)

* (0) 題外話，寫這篇時，我想到剛學完 C 語言不久時，以前查 memory leak 的方法真的很笨。

(1) 寫完之後才發現，這篇實做做得很差，原因後面會再講。

(2) 大多作之 dbg_malloc 所使用的架構會再複雜一些，如會使用 union + struct，有些還會考慮 block。

在 part (I) lookup memory leak 時筆者曾提到使用 visual C++ 方式查 memory leak。一種實作是將所有之配置函式全都先寫另一 dbg 版本額外呼叫，如

malloc   --> dbg_malloc
calloc    -->  dbg_calloc
recalloc --> dbg_recalloc
free      ---> dbg_free

mem** 系列函式之實作本身意義不大，但有些人還是會實作。

這裡只以 dbg_malloc / dbg_free 為例說明。目前大多開發技巧之作法 ( VC 確實也是這麼做 ) ，是先定義一份維護記憶體資訊之 linklist 出來 ，這裡以單向為實作，且是弄 signle list, head WITH value，和一般 DS 課本提的可能有所不同。

同時做 static global variable 。再來把 dbg_malloc / dbg_free 等相關函式全寫好，而其 prototype 可由 coder 自定，目前所定義之 prototype 大多如下

src_file 指的是原始檔名 (如 main.c)，line 是程式碼之行號，考慮一些 compiler 提供之自家 macro，少數人會加入 const char* func_name 。接下來進行條件式編譯。

上述之 __FILE__ 指的是呼叫端之檔名， __LINE__ 是呼叫端之行號，若要加 function name，vc 為 __FUNCTION__，GNU 為 __func__。我們用的只是提供一個跳板，當在其他程式碼 (如 main.c) 裡定義了 DBG_MALLOC 時，就會自動將 malloc / free 換成 dbg_*** 版本。

而 dbg_malloc 做的事情包含了記錄 caller 資訊外 (filename, lineno, size)，必須把實際 malloc 所傳回之實際值記錄下來，以便之後釋放 free 時能正確執行，而 dbg_malloc 實際上又有兩種作法。

一種是先 allocate Stack，然後 Stack 再 allocate 出所需的大小，並記錄其位置。所以 struct 裡面必須還要多一欄位叫 void * ptr，這裡不再贅述。

另一種較常見之 allocate 記憶體配置圖如下

示例碼如下。

而 dbg_free 時，由於傳入之 pointer 已事先 + sizeof(Stack)，故要找該 node 之開頭，必須先將引數 - sizeof(Stack)，再將 pointer 移出 ，釋放就行，關鍵碼大概如此。

 ptr = (Stack*)ptr-1; // offset struct size 
 tmp = head;
 while(tmp != NULL && tmp!=ptr) tmp = tmp->next;
 if (tmp == ptr) /* remove tmp from list */ 
else /* expection */ 

觀念是這樣，但考慮 except ，寫起來有點長。

 接下來還要再做一個動作，就是在程式結束前，把 link list 資訊全都顯示出來，假設叫 dbg_report。

 完成之後，要看還沒被釋放的 memory ，直接調用 dbg_report 即可，一般是放在 main 之最後。一份使用的範例如下。

#define DBG_MALLOC // if want to use dbg_***, define this first
#include "dbg_malloc.h"
#include <stdlib.h>
#include <stdio.h>
int main()
{
    size_t i;
    char* arr;

    arr = (char*)malloc(10);    
    // we can normal use it
    for(i=0; i<10; ++i) arr[i] = i;
    for(i=0; i<10; ++i) printf("%d", arr[i]);
    
    arr = (char*)malloc(20);     
    arr = (char*)malloc(30);
    arr = (char*)malloc(40);

    // has 4 memory leak
    dbg_report();
    getchar();
    return 0;
}

便可看到 memory leak 相關資訊。提醒一點的是，若為獨立式編譯也要測 memory leak，必須在個別之 .c / .cpp 引入自己寫好的 dbg_malloc.h ，還要再定義出 DBG_MALLOC，該檔才可正常使用 dbg_****  (簡單的說，具有 scope 問題)。

一此使用範例碼，下載  dbg_malloc_3.1-20130110.rar ，裡面除了 dbg_malloc / dbg_free 外，還實作了 dbg_realloc / dbg_calloc 。接下來是檢討時間。

(1) some exception

上面所述之情況都假設了 coder 不會亂來，也就是假設 allocate 一塊 heap 範圍是 [X, Y] ， coder 回傳的一定是  X，而不會是其他 pointer。但這種假設並不非常合理，不論是有意、無意之情況下，它都會發生，特別是在寫底層動作的時候。這問題有兩種看法，一種是不管它，直接轉交 library 去做，但這樣便失去了這份 dbg_malloc 意義，故筆者傾向去把它抓出來。

void free(void *param);

一般在正常釋放時，會往前 offeset 一個 MemInfo 大小再釋放，但此處我們沒辦法得知 (Stack*)(param) - 1; 是否存在 linklist 裡，故還是必須逐一 polling ，才能抓出這方面之錯誤，此時不論 double link 或 single link 在 travel 都是 O(n)。

一般在考慮 coder 使用 heap 之情況，大多時候是符合堆疊特性，這也是為什麼強調在 allocate 時，做 push_front ，別做 push_back，減少搜尋時間。

(2) output message

上述之輸出是用很無腦的 printf / puts 到 stdin，好一點點無腦的方式是輸出到檔案，在 dbg_report 時寫入該檔，直接用某軟體 (如 notepad.exe、pspad.exe ) 直接開啟。然而實際上要做強大與 portable，勢必要換其他方法，且部份特性將依賴於 compiler IDE 與其 library，還必須制定一套嚴謹之條件式編譯。下面是目前認為可以玩的地方。

(a) 將訊息輸出到特定 IDE：VS user 可參考這篇文章，要做好一點的話，要花點設計 macro like function 要怎麼寫。另我記得曾看過某份教學，有提到只要安裝一份 Viewer，便可把 訊息顯示於該 Viewer ，還要再找過。

(b) 納入 Windows Programming 技巧：dbg_report 時使用 CreateWindow 建立一視窗出來，並顯示訊息，這應是較具可攜性作法，只要 OS 版本相同大致都可用。

(3)  defect memory leak in C++ ??

C++ 方面沒深入研究真正做法為何，不敢妄下定論，但有  實際 trace 過 new  之 coder 將知道，在部份條件下它調用的還是屬於 malloc 類 function，唯標準裡應無明確規定這點。

(5) access right

這已經超出探討之議題，實作上不會再調用 standard library，而是調用了更底層之 API，如 Win32 VirtualAlloc / VirtualAllocEx，裡面可設置 memory protected constant 進行限制。LINUX 系列可再找過 < 真的不是筆者強項 >

(6) HEXSPEAK

在 vc debug 監看式裡，沒被初始化的變數會出現 0xCC，4 bytes 的話變成 0xCCCCCCCC，這種作法有不少解讀，像有些人認為是特定的 magic number，allocate 沒用是 0xCCCCCCCC，delete 後變 0xDDDDDDDD；一些其他平台也有 0xDEADBEEF (死牛肉的故事。傳聞，這竟然會是 google 面試題之一，explain the significanance of "dead beef" ，裡面的回答還不錯)，這些東西被統稱作 HEXSPEAK。

(7) open source

目前針對 C language 做 defect memory leak 之 open source，整體寫得較完整，又容易懂的應屬 sourcefroge 裡之 memlak，有興趣可抓下來研究其原始碼。

9. alignment allocate memory

(1) 我必須承認，這篇我在 pointer 用的 data type 並不非常適當 (犯懶，有機會再寫 for gernal)。

(2) intptr_t 放在 stdint.h 裡面，它是將 pointer address 硬轉成一個常數的 data type，VC 到 2010 才提供，但上網查可拿到 portable 版本。

(3) ptr_difft 放在 stddef.h 裡面，若手邊 compiler 沒有還是可以上網找 protable version，但比較麻煩的是，切割成 file 獨立編譯時，容易與 stdlib.h 相衝，這現象試過 gcc , vc，有空再研究是怎麼回事。

(4) 所有的 ALIGN 均假設為 2 之正整數次方。

這東西還是昨天才知道的，想過之後解法方法應不只一種，觀念上應都大同小異，但敘述上會花些時間。這問題常發生在寫 driver 上，可能基於某種限制，必須將存放資料之 pointer 存放在 1K, 2K, 4K... 位置上。但卻又不能保證，用 malloc / new 傳回的會是在上面。

我們把問題先縮減、定義清楚，方便說明，以下address 以 8 bits 示之。現假設欲 aligned 起始位置為 8 之倍數，所以 aligned 後之起始位置應該要是 0x***0、0x***8。

假設 char *base= (char*)malloc(5)，且返回之位置是 0x12，怎麼將 base aligned 到 0X18？先看一下它的配置圖

如果能移到 ret 那是最好的事，但實際上卻沒辦法，作法是，將 ret 之前的位置一起 allocate ，變成下面這張配置圖

以這例子而言，實際上是 allocate 11 bytes，其中 base 後之 6 bytes 是為了達到 alignment 而多配置的，到時候在使用的時候從 ret 開始即可，而釋放時從 base 開始譯放。那麼問題就變成了：傳回一個 pointer (事實上這個 pointer 到時要轉成 value 看待)，要怎麼找到最接近它的 alignment address ?

我們重新把變數寫一遍吧。

const size_t SIZE  = 5U;
const size_t ALIGN = 8U;
char *base, *ret;

step 1 : 多配置記憶體

看一下這區間： base ~ base+7 之間，一定有一個數值可以被 8 整除；一樣的，base~base+(ALIGN-1)，一定存在一個數可被 ALIGN 整除，再加上原本的 SIZE，所以應配置的空間就變成了  SIZE + ALIGN-1，而且還可以確定，在這區間裡面，只有一個數值可剛好被 ALIGN 整除 (有興趣網友可想一下為什麼或證明之類)。  base = (char*) malloc (SIZE + ALIGN - 1);

step 2 : 計算[ base, base + ALIGN - 1] 之 alignment address - ret

一開始我們必須先把最後一塊位置址取出來，也就是將  base + ALIGN - 1 當數值看待，當一般數值看待 ： 

 (intptr_t)(base + ALIGN - 1);  

假設取出來的數值叫 value = 0x1c ，這裡用到一點 bitwise 技巧。

0001 1100  (value 二進位 )
0000 1000  (ALIGN 二進位)

 如果，能將上面 value 之黃底部份全都清零，變成 0001 1000  ，那就剛好 ALIGN，要清 bit0:bit2 (3bits) 很簡單，只是做  & 1111 1000 就行，
 

　0001 1100  (value 二進位 )
＆1111 1000   ( = ~0000 0111)
－－－－－－－－－－－－－－－－－
　0001 1000   (得到 ret) 
 

推一下 1111 1000 = ~(0000 0111)，這個值剛好就是 ALIGN 扣 1 後再取反向，接下來就得到 ret。整個推導下來，在 bitwise 部份成立的條件便是： ALIGN 必須是 2 之正整數次方，也不能等於零，等於零會使得 ret 變 0 ，到時傳回去就變 memory leak，這便是這種方法之限制。

ret = (char*) /* 硬轉型 */
         ((intptr_t)(base+ALIGN - 1) /* 先取得 base 最後元素位置，硬轉成數值 */
         & ~ (ALIGN - 1)); /* 再和 (ALIGN-1) 之反向做 and 運算 */

此後直接對 ret 進行操作即可，在釋放時就直接對 base 釋放。程式碼如下示例。

#include <stdio.h>
#include <stdlib.h>

int main()
{
    const size_t SIZE  = 100U;
    const size_t ALIGN = 32U;
    size_t i;
    char *base, *ret;

    base = (char*)malloc(SIZE + ALIGN - 1U);
    ret = (char*)((intptr_t)(base+ALIGN - 1)& ~ (ALIGN - 1));

    printf("base = %#p, ret=%#p\n", base, ret);
    for(i=0; i<SIZE; ++i) ret[i] = i;
    
    free(base);
    getchar();
    return 0;
}

如果本身 allocate 之起始位置就 aligned 時，base 與 ret 將會指向同一個位置，在釋放時不用擔心會出包 (只需要擔心 ALIGN  不是 2 的整數次方)。

現在又有一個問題了，包 function 怎麼包？包 function 時必須同時考慮到能夠正常 allocate 、free，但所需要的指標是二個，怎麼包？第一種想法記憶體配置圖參考如下 (這不是好的想法 )。

方法是直接在申請的空間後面，再加上個 sizoef(void *) 大小，去記錄原本的 base 是位在哪裡，但進行 free( param) 時由於不會傳入 Size，所以根本不知道紀錄 base 位置到底在哪，若要用成 free(param, size) 就丟臉了。較合理之配置應如下

將記錄 base 位置直接放到 ret 前一個位置，如此在傳入 free(param) 時，只需往前 offset 一個 sizeof(ptr)，便可得到位置值。

void *align_malloc( size_t size, size_t align )
{
    void *base, *ret;
    
    /* allocate total_size */
    if(!(base=malloc((size+align-1)+sizeof(void *)))) 
        return NULL;

    /* aligned address - ret */
    ret=(void*)( ((intptr_t)base+sizeof(void *)+align-1)&~(align-1) );

    /* (base value) assigned to (ret offset 1 sizeof(void*) )*/
    *((void **)ret-1)=base;    
    return ret;
}

void align_free( void * param )
{
    if(param)    free(* ((void **)param-1));
}

其他的寫法可到  stackoverflow 參考  Solve the memory alignment in C interview question that stumped me 這份文章，概念上大同小異。另外這部份其實 comopiler 大多會提供自己額外的 function 做這些事，VC 提供的 CRT libary 便有 一系列 function處理這問題。而 gcc 則提供了一系列之 POSIX_MEMALIGN function 處理這問題。

A. others

有些用法筆者認為冷僻，覺得知道似乎也不會帶來加分效果，像是在網路上較有名的一段 code

int a[10], *p = a;
p[0]=10;       // a[0] = 10
(p+1)[0]=10;   // a[1] = 10
0[p + 1] = 10; // = (p+1)[0] = p[1] = 10
( &a )[0][0] = 20; // (&a)[0] = a[0]
0[&a][0] = 30;     // 0[&a][0] = a[0]
a[0] = "0123456789ABCDEF" [0]; // 該字串取第0個元素

這些問題認為實用不大，何況實際也不會有人這麼寫 ( 應該不會有吧.. )，就像是便不再贅述。

B. Q & A

這些 Q & A 有些和指標較為相關，但實在難分辨到底屬 array 還是 pointer 問題 (畢竟本身相關係蠻大)，也予以收錄筆記。 

[Q 001] int a[10]; 書上寫 sizeof(&a) 等於 4 ，但我實際執行時卻跑出 40 ？

[A 001] sizeof(&a) = sizeof( void * )，然而跑出 sizeof (&a) = sizeof (a) 代表該換 compiler 了， VC6.0 這部份實做是錯的。

[Q 002]  什麼是鋸齒狀陣列 ？

[A 002]  拿二維陣列來說，鋸齒狀陣列 (saw array) 指的是每一維的長度不一定相等。

[Q 003] 鋸齒狀陣列 (saw array) 是不是只能先 allocate 二維指標，再 allocate 一維部份做處理(範例碼如下)？有沒有比較好的解決方案？

#define DIM1 5

const size_t DIM2[DIM1] = {2,3,4,5,6};
int i, **arr;
//allocate
**arr = (int*)malloc(sizeof(*arr)*DIM1);
for(i=0; i<DIM1; ++i) 
    arr[i] = (int*)malloc(sizeof(**arr) * DIM2[i]);
// release
for(i=0; i<DIM1; ++i) free(arr[i]);
free(arr);

[A 003] 

 基本上，不是，可以再參考 上一篇文章 提到的 allocate memory for 2d 方式做調整，可去下載裡面提到的 ArrayManagement.rar 。我以 O(1) 之配置包成 function 做示例碼 (隨手寫寫，但驗證是正常)，O(n) 較簡單可再仔細想一下當 HW。

#define ARR_H 3
// allocate two dim saw array
void** saw_malloc(size_t SizeOfEle, size_t H, size_t *W)
{
    char ** space2d;
    char * space1d;
    size_t i, size;

    // defect error
    if(H==0U || W==NULL) return NULL;
    // calculate memory space
    for(size=i=0U ; i<H; ++i) size+=W[i];
    size*=SizeOfEle;
    // allocate memory
    space2d = (char **)malloc(sizeof( char *)*H + size ); 
    // connect pointer
    space1d = (char *)(space2d+H);
    for(i=0; i<H; ++i){
        space2d [i] = space1d;
        space1d += SizeOfEle * W[i];
    }
    return (void**)space2d;    
}
/* caller */
#define ARR_H 3
size_t H = ARR_H;
size_t W[ARR_H] = {2,3,4};
/* allocate */
int **arr = (int**)saw_malloc(sizeof(int), H, W);
/* dosomething and release */
free(arr);

要調用 memse / memcpy : memset( *arr, 0, sizeof(*arr)*H*W)， 維度再上去 (如 for 3d, for 4d...  ) 自己再想著推。

[Q 004] 陣列大，有辦法增加 cache hit 嗎？

[A 004] 

這問我我也沒辦法給確定的答案，目前常被注意的有三個項目，這個在簡體中文的維基百科裡面有提及，裡面提到的 blocking 所用的例子便是大型矩陣乘法提到 cache hit 問題，stackoverflow 也有類似的討論。一點冷知識，在 Expert C Programming 7.4 裡提到，由於 dst[65536] 與 src[65536] 都是 cache 容量之整數倍數，加上標籤優化之問題，使得 ( dst[i] = src[i]  ) src, dst 不會同時出現在 cache 裡，造成逐一 assigned 時效能降低。 (妙的是 memcpy 解決了這問題)。

C. Reference

[1] wiki - SPEAKHEX

[2] stackoverflow-Solve the memory alignment in C interview question that stumped me 

[3] MSDN - Data Alignment

[4] POSIX_MEMALIGN function

[5] MSDN -  VirtualAlloc 

[7] stackoverflow - How does one write code that best utilizes the CPU cache to improve performance?

[6] Expert C Programming: Deep C Secrets - By Peter van der Linden