這裡是 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 課本提的可能有所不同。

 

Code Snippet
  1. typedef struct tagStackmallmalloc{
  2.     const char * fname;
  3.     size_t line_no, size;
  4.     struct tagStack * next;
  5. }Stack;
  6.  
  7. Stack head;

 

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

 

Code Snippet
  1. void * dbg_malloc(size_t size, const char * fname, size_t line_no);
  2. void * dbg_calloc(size_t num , size_t size , const char * fname, size_t line_no);
  3. void * dbg_realloc( void * ptr , size_t size , const char * fname, size_t line_no);
  4. void dbg_free( void * ptr );
  5. void dbg_report();

 

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

 

Code Snippet
  1. #  ifdef DBG_MALLOC
  2. #    define malloc(size) dbg_malloc(size,__FILE__,__LINE__)
  3. #    define calloc(num,size) dbg_calloc(num,size,__FILE__,__LINE__)
  4. #    define realloc(num,size) dbg_realloc(num,size,__FILE__,__LINE__)
  5. #    define free(ptr)    dbg_free(ptr)
  6. #  endif

上述之 __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 記憶體配置圖如下

 

實際大小

Sizeof(Stack)

size

Struct 配置

Stack 實體

實際傳回之位置

 

示例碼如下。

Code Snippet
  1.  
  2. typedef struct tagStackmallmalloc{
  3.     const char * fname;
  4.     size_t line_no, size;
  5.     struct tagStack * next;
  6. }Stack;
  7.  
  8. Stack head;
  9.  
  10.  
  11. /**
  12. * @brief defect memory leak for malloc function
  13. * @param size     allocate size
  14. * @param fname    function name of caller
  15. * @param line_no  code of line
  16. * @return         success return pointer to heap, fail return NULL
  17. */
  18. void * dbg_malloc(size_t size, const char * fname, size_t line_no)
  19. {
  20.     Stack * new_node = (Stack*)malloc(size + sizeof(Stack));
  21.     if(!new_node) return NULL; // Allocate fail.
  22.  
  23.     new_node->size    = size;
  24.     new_node->fname   = fname;
  25.     new_node->line_no = line_no;
  26.  
  27.     new_node->next = head.next;
  28.     head.next      = (struct tagStack*)new_node;
  29.     return (void*)(new_node+1);
  30. }

 

而 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 ,寫起來有點長。

 

Code Snippet
  1. /**
  2. * @brief defect over free or ill free for free function
  3. * @param ptr  want to release pointer
  4. * @return no return value
  5. */
  6.    voiddbg_free( void * ptr )
  7. {
  8.     Stack * cur , * nxt;
  9.     if(ptr==NULL) { // Release a Null pointer
  10.         fputs("\n[dbg_free error] : Release a NULL pointer.\n", stderr);
  11.         assert(0);
  12.         return ;
  13.     }
  14.     for(cur = (Stack*)&head, nxt = (Stack*)cur->next;
  15.         nxt;
  16.         cur=nxt, nxt = (Stack*)nxt->next)
  17.     {
  18.          if( (void*)(nxt+1)==ptr) { // Find to free
  19.             cur->next = nxt->next;
  20.             free( (void*) nxt);
  21.             return ;
  22.         }
  23.     }
  24.     // can't find any pointer match ptr
  25.     fputs("\n[dbg_free error] : Release a ill pointer.\n", stderr);
  26.     assert(0);
  27.     return;
  28. }

 

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

 

Code Snippet
  1. /**
  2. * @brief look up memory leak
  3. * @param no input param
  4. * @return no return value
  5. */
  6.    voiddbg_report()
  7. {
  8.     if(!head.next) fputs("\n[memory clear!!]\n", stderr);
  9.     else {
  10.         size_t no=0, i;
  11.         Stack * cur ;
  12.         unsigned char  * beg , * end;
  13.  
  14.         fputs("\n**********************\n", stderr);
  15.         for(cur = (Stack*)head.next ; cur ; cur = (Stack*)cur->next){
  16.             fprintf(stderr, "[memory leak %2u]\n", ++no);
  17.             fprintf(stderr, "   file : %s\n", cur->fname);
  18.             fprintf(stderr, "   line : %u\n", cur->line_no);
  19.             fprintf(stderr, "   addr : %p\n", (void*)(cur+1));
  20.             fprintf(stderr, "   size : %u", cur->size);
  21.  
  22.             for(beg = (unsigned char*)(cur+1) , end = beg + cur->size , i=0;
  23.                 beg != end ;
  24.                 ++i, ++beg)
  25.             {
  26.                 if(i%16==0) fputs("\n          ", stderr);
  27.                 fprintf(stderr, "%02x ", *beg);
  28.             }
  29.         }
  30.         fputs("\n", stderr);
  31.     }
  32. }

 

 完成之後,要看還沒被釋放的 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?先看一下它的配置圖

 

address

0x12

0x13

0x14

0x15

0x16

0x17

0x18

0x19

0x1a

0x1b

0x1c

pointer

base

(2)

(3)

(4)

(5)

 

ret

       

 

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

 

address

0x12

0x13

0x14

0x15

0x16

0x17

0x18

0x19

0x1a

0x1b

0x1c

pointer

base

Nul

Nul

Nul

Nul

Nul

ret

(2)

(3)

(4)

(5)

 

以這例子而言,實際上是 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,但所需要的指標是二個,怎麼包?第一種想法記憶體配置圖參考如下 (這不是好的想法 )。

 

空間說明

為了 alignment 所浪費之空間

申請出來

之空間

紀錄base之位置

變數

(base)

(ret)

(base_adr)

大小

???

Size

Sizeof(ptr)

 

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

 

空間說明

為了 alignment 所浪費之空間

紀錄base之位置

申請出來

之空間

變數

(base)

(base_adr)

(ret)

大小

???

Sizeof(ptr)

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

edisonx 發表在 痞客邦 PIXNET 留言(0) 人氣()