[C++][Malloc] Explicit allocator 구조와 구현

출처 : https://www.preqin.com/about/partners/partner/allocator

 

 

 

오늘은 C 와 C++에서 사용되는 Malloc 의 구현 방식인 Explicit allocator에 대해서 공부해 보려고 한다.

 

그 전에 사전 지식을 조금 먼저 이야기를 해보겠다.

 

 

Dynamic Memory Allocation 이란??

프로세스의 메모리 구조

 

@ 프로그램이 작동하는 도중 (런타임 동안) 필요한 메모리를 할당 받고자 할 때 사용 하는 할당 방법

@ 프로세스의 Heap 공간에 저장 -> 단편화(Fragmentation) 문제 발생 가능

@ 단편화 문제를 해결하고 효과적으로 메모리들을 저장하기 위한 Dynamic allocator로 Explicit Allocator , Implicit Allocator 등 이 존재한다.

 

 

사용 이유

 

: 효율적인 메모리 관리

 

 

Block 이란?

메모리를 관리하는 단위

 

 

< Block 구성 > ( Explicit allocator )

 

[Header , Prev block pointer , Next block pointer , Payloading , Padding , Footer]

 

Header , Footer : 각각 블록의 시작과 끝을 나타내는 부분, 블록의 사이즈와 할당 여부를 저장한다. 

Prev block pointer, Next Block pointer : 가용 블록들끼리 포인터들로 연결 시키기 위해 사용하는 블록 포인터 ( 이중 연결리스트 형태 )

Payload : 실제 정보들이 들어가는 부분

Padding : 8Bytes 단위를 맞추기 위해 할당해야 할 메모리보다 많은 메모리를 할당해줌 (선택적으로 사용한다.)

Header , Footer , Pointers 들은 각각 32 bit 운영 체제 기준 4 Bytes 이다.

 

Memory는 이런 블록들로 구성되어 Heap 속에 저장되어 있다.

 

블록 들을 저장하는 방법에 따라 Explicit Allocator , Implicit Allocator 두 가지 할당기로 나뉘게 된다.

여기에서는 C / C ++ 에서 사용하는 Explicit Allocator에 대해서 배워 보겠다.

 

 

Explicit Allocator

 

 

@ 응용 프로그램이 직접 메모리를 할당 / 반환하는 방식의 Allocator

@ 할당이 해제 된 가용 블록들을 연결리스트 형태로 관리 ( Prev , Next block pointer 사용 )

@ C 나 C++ 와 같은 low-level 언어에서 사용

 

 

 

연결 리스트에 블록을 추가하는 방법

 

1)    Ordered List : 순서대로 추가

2)    LIFO( Last-In-First-Out ) : Stack 처럼 작동

 

 

Ordered List는 자신의 순서를 연결리스트에서 찾아야 하므로 linear time이 걸림.

LIFO List의 경우 바로 집어넣으면 되기 때문에 Constant time이 걸린다.

 

일반적으로LIFO 방식이 성능 적인 면에서 우세 하다.

 

 

LIFO를 이용한 Explicit Allocator의 Heap 구조

 

0x08블록은 할당되었지만 연결리스트에 들어 있는 이유는 그저 연결리스트의 마지막을 나타내주기 위함이다.

새로운 가용 블록이 생기면 연결리스트 맨 앞에 붙게 된다.

 

 

---

이제 그럼 LIFO 방식의 Explicit Allocator를 구현 해보자

C++ 을 사용하여 구현 하였다.

 

 

맴버 변수

 

char* heap ;        // Start point of Heap                      
char* brk;          // End point of Heap
char* max_addr;     // Max Address of Heap
char* free_list;    // Pointing Front Free Block

 

 

 

매크로

 

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// MACRO ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 

 
/**
 * @brief Macros for Size
 */

#define WSIZE 4                     // 1 BYTE
#define DSIZE 8                     // Double BYTE 
#define MAX_HEAP 100 * (1<<20)      // Maximum of HEAP 100 MB
#define CHUNKSIZE (1<<9)            // Size for Heap increasement ( 256 Bytes )


/**
 * @brief Macros for Block Size & Alloc 
 */

#define PACK(size, alloc) ((size) | (alloc))    // Block Size( Multiple of 8. using 29 bit ) + IsAlloc( 000 : Free / 001 Alloc using 3 bit 0~7 ) 

#define GET(p) (*(unsigned int*)p)              // From Pointer p, getting 'int information'( PACK(size, alloc) )
#define PUT(p,val) (*(unsigned int*)(p) = val)  // Putting 'int value' to Pointer P

#define GET_SIZE(p) (GET(p) & (~0x7))           // Getting Block Size information
#define GET_ALLOC(p) (GET(p) & (0x1))           // Getting IsAllock information


/**
 * @brief Macros for Block
 */

#define HDBP(bp) ((char *)bp - WSIZE)                                               // Header Block of bp
#define FTBP(bp) ((char *)bp + GET_SIZE(HDBP(bp)) - DSIZE)                          // Footer Block of bp

#define NEXT_BLKP(bp) ((char*)(bp) + GET_SIZE(HDBP(bp)))                    // Next Block of bp
#define PREV_BLKP(bp) ((char*)(bp) - GET_SIZE( ((char *)(bp) - DSIZE )))      // Previous Block of bp




/**
 * @brief Macros for free List Macros
 */

#define GET_PREV(bp) (*(void**)bp)                                          // Prev Block Pointer of bp
#define GET_NEXT(bp) (*(void**)((char *)bp+WSIZE))                                  // Next Block Pointer of bp

#define PREV_A_TO_B(bp1,bp2) (*(void **)bp1 = bp2)                          // Connecting Prev BP of bp1 to Address which is pointed by bp2  
#define NEXT_A_TO_B(bp1,bp2) (*(void **)((char*)bp1+WSIZE) = bp2)                  // Connecting Next BP of bp1 to Address which is pointed by bp2

 

 

매크로가 정말 많다.

 

PACK : Header 와 Footer에 필요한 Size , Alloc여부를 합쳐주는 매크로

 

GET , PET : void * 가 인자로 주어지므로 int 값을 얻기 위해 형 변환 진행

GET_SIZE , GET_ALLOC : PACK에서 각각 size 와 alloc 여부를 뽑아냄

 

HDBP , FTBP : 각각 Header와 Footer를 가리키는 pointer를 반환

PREV_BLKP , NEXT_BLKP : 각각 이전 , 다음 블록으로 이동하는 매크로

 

GET_PREV , GET_NEXT : 각각 PREV, NEXT pointer가 가리키는 block 반환

PREV_A_TO_B : A의 PREV pointer가 B가 가리키는 곳을 가리킴

NEXT_A_TO_B : A의 NEXT pointer가 B가 가리키는 곳을 가리킴

 

 

---

서브 함수들

 

 

 

Extend_heap , Mem_sbrk 함수

 

Heap을 늘려 주는 함수

 

mem_sbrk : heap 크기를 늘려줌

extend_heap : heap이 늘어남에 따라 블록 조정을 해줌

 

/**
 * @brief The function that increases space of heap when it is lack
 * 
 * @param words : Number of words ( word : 4 Bytes ) 
 * @return void* : New Free block pointer
 */

void * Mymalloc::extend_heap (size_t words)
{    

    void *bp;
    size_t size;
    
    size = (words % 2) ? (words +1) * WSIZE : words * WSIZE;    // Double Word (8) Alignment
    
    if((bp = mem_sbrk(size)) == (void *) -1) return (void *)-1;
    
    // Modifying header and footer

    PUT(HDBP(bp),PACK(size , 0));
    PUT(FTBP(bp) ,PACK(size , 0));
    PUT(HDBP(NEXT_BLKP(bp)) , PACK(0,1));  // Moving Last block

    return coalesce(bp);                   // If the previous block is not allocated, combine the two blocks
}


/**
 * @brief The function that increases the size of the heap
 * 
 * @param incr : Amount of increasement of heap
 * @return void* : Brk pointer before increasement
 */
void* Mymalloc::mem_sbrk(int incr){
    char* old_brk = brk;    

    if( (incr < 0) || ( (brk + incr) > max_addr) ){     // Error
        perror("mem_sbrk failed.");
        return (void *)-1;
    }
    
    brk += incr;            // Heap Size increases

    
    if(old_brk == heap) cout << "[ Heap Increasement ] " <<" Before : " << old_brk-heap << " Bytes " << " -> " <<" After : " << brk-heap << " Bytes " << " [ + " << incr <<" Bytes ] " << endl;
    else cout << "[ Heap Increasement ] " <<" Before : " << old_brk-(heap - DSIZE) << " Bytes " << " -> " <<" After : " << brk-(heap - DSIZE) << " Bytes " << " [ + " << incr <<" Bytes ] " << endl;

    return (void *)old_brk;  // return previous brk
}

 

 

주석으로 설명을 많이 적어 두었다!!

 

 

 

 

Disconnect ,New_connect , Coalesce 함수

 

Disconnect : 가용 블록이 사용을 위해 할당되었을 때 가용 블록 연결 리스트에서 제거 하는 함수

New_connect : 새로 생긴 가용 블록을 가용 블록 연결 리스트에 LIFO 방식으로 연결하는 함수

Coalesce : 가용 블록이 생겼을 때 바로 옆에 가용 블록이 있다면 합치는 함수 ( 단편화를 줄이기 위함 )

 

 

/**
 * @brief The function that disconnects the free block pointed by bp from the free list
 * 
 * @param bp : Pointer which is pointing to use free block
 */
void Mymalloc::disconnect(void * bp){
    
    void* prev = (void *)GET_PREV(bp);
    void* next = (void *)GET_NEXT(bp);
        
    if(prev) {
        if(!next) NEXT_A_TO_B(prev,NULL);
        else NEXT_A_TO_B(prev, next);
    }
    if(next){
        if(!prev){ PREV_A_TO_B(next,NULL); free_list = (char *)next; }
        else PREV_A_TO_B(next,prev);
    } 

    PREV_A_TO_B(bp,NULL);
    NEXT_A_TO_B(bp,NULL);

}


/**
 * @brief The function that connects the free block pointed by bp to the free list (LIFO order).
 * 
 * @param bp : pointer which is pointing new free block.
 */

void Mymalloc ::new_connect(void * bp){

    PREV_A_TO_B(bp , NULL);
    NEXT_A_TO_B(bp,free_list);

    PREV_A_TO_B(free_list , bp);
    
    free_list = (char *)bp;

}


/**
 * @brief The function that combines the free blocks
 * 
 * @param bp : Pointer which is pointing free block
 * @return void* : Pointer which is pointing combined free block
 */

void * Mymalloc::coalesce(void *bp){
    
    size_t size = GET_SIZE(HDBP(bp));                       // Size of bp's block
    size_t prev_alloc = GET_ALLOC(HDBP(PREV_BLKP(bp)));     // Isalloc of Prev block of bp 
    size_t next_alloc = GET_ALLOC(HDBP(NEXT_BLKP(bp)));     // Isallco if Next block of bp


    // Case 0 (For realloc)
    // Curr block is Allocated
    // Next block is free block
    if(GET_ALLOC(HDBP(bp)) == 1 && next_alloc == 0){
       
       // Next block disconnect
       disconnect(NEXT_BLKP(bp));
       
       // Combining Curr block + Next block
       size += GET_SIZE(HDBP(NEXT_BLKP(bp)));
       PUT(HDBP(bp) , PACK(size , 1));
       PUT(FTBP(bp) , PACK(size , 1));

        return bp;
    }

    // Case 1
    // Prev & Next block are allocated blocks
    if(prev_alloc == 1 && next_alloc == 1){

        // New Free block connect
        new_connect(bp);

        return bp;
    }

    // Case 2
    // Prev block is free block
    // Next block is allocated block
    else if( prev_alloc == 0  && next_alloc == 1){

        // Combining Block Prev block + Curr block
        size += GET_SIZE(HDBP(PREV_BLKP(bp)));
        PUT(HDBP(PREV_BLKP(bp)),PACK(size , 0));
        PUT(FTBP(bp), PACK(size,0));

        // prev free block disconnect
        disconnect(PREV_BLKP(bp));

        // New Free block connect
        bp = PREV_BLKP(bp);
        
        new_connect(bp);

    }

    // Case 3
    // Prev block is allocated block
    // Next block is free block
    else if(prev_alloc == 1 && next_alloc == 0 ) {

        // Next free block disconnect
        
        disconnect(NEXT_BLKP(bp));

        // Combining Block Curr block + Next block
        size += GET_SIZE( HDBP(NEXT_BLKP(bp)));
        PUT(HDBP(bp), PACK(size,0));
        PUT(FTBP(bp) , PACK(size,0));

        // New Free block connect
        new_connect(bp);

    }

    // Case 4
    // Prev & Next block are free block
    else{

        // Combining Block Prev block + Curr block + Next block
        size += GET_SIZE(HDBP(PREV_BLKP(bp))) + GET_SIZE(HDBP(NEXT_BLKP(bp)));
        PUT( HDBP(PREV_BLKP(bp)) , PACK(size , 0));
        PUT( FTBP(NEXT_BLKP(bp)), PACK(size,0));

        // Prev , Next free block disconnect
       
        disconnect(PREV_BLKP(bp));
        disconnect(NEXT_BLKP(bp));


        // New Free block connect
        bp = PREV_BLKP(bp);

        new_connect(bp);

    }

    return bp;
}

 

주석 참고!!

 

 

 

Find_Fit , Place 함수

 

 

메모리 할당을 도와주는 함수

 

Find_fit : 사용하기에 알맞은 가용 블록을 찾아 주는 함수

Place : 가용 블록 할당 후 블록의 남은 부분을 다시 가용 블록으로 만들어 주는 함수

 

 

/**
 * @brief The function that searches fit free block, in free list (LIFO order)
 * 
 * @param asize : Demanded size
 * @return void* : Pointer which is pointing fit free block. ( IF there isn't, return nullptr )
 */
void * Mymalloc::find_fit(size_t asize){
    void* bp;

    for(bp = (void *)free_list ; GET_ALLOC(HDBP(bp)) == 0 ; bp = GET_NEXT(bp) ){   // Finding list
        if(GET_SIZE(HDBP(bp)) >= asize) return bp;  // fit
    }

    return nullptr;
}


/**
 * @brief The function that put the remaining block back in the free list again, when Free block is too large
 * 
 * @param bp : Pointer which is pointing large free block
 * @param asize : Size of large free block
 */
void Mymalloc::place(void *bp, size_t asize){

    size_t csize = GET_SIZE(HDBP(bp));

    if((csize - asize) >= 2 * DSIZE){
        PUT(HDBP(bp) , PACK(asize , 1));
        PUT(FTBP(bp) , PACK(asize , 1));

        PUT(HDBP(NEXT_BLKP(bp)), PACK(csize-asize , 0));
        PUT(FTBP(NEXT_BLKP(bp)), PACK(csize-asize , 0));

        new_connect(NEXT_BLKP(bp));

    }   
    else{
        PUT(HDBP(bp) , PACK(csize , 1));
        PUT(FTBP(bp) , PACK(csize, 1));
    }

    // Disconnecting allocated block from free list
    disconnect(bp);

}

 

 

---

Malloc 함수들 ( Malloc , Calloc , Realloc , Free)

 

 

 

 

1) init 초기화

 

Malloc을 위한 준비

 

/**
 * @brief Heap initalization for allocation
 */
void Mymalloc::mm_init(){

    cout << "[ Heap init ] Heap is initalized. " << endl;

    if( ( mem_sbrk(6 * WSIZE)) == (void *)-1 ) return ;  // Padding + Header + Prev Pointer + Next Pointer + Footer + Last Block

    PUT(heap , 0);                                      // Padding
    PUT(heap + 1 * WSIZE , PACK( 2 * DSIZE , 1));       // Header
    PREV_A_TO_B((heap+ 2 * WSIZE) , NULL);              // Prev Pointer
    
    
    free_list = heap + (2 * WSIZE);                     // free list init

    NEXT_A_TO_B((heap+ 2 * WSIZE) , NULL);              // Next Pointer
    PUT(heap + 4 * WSIZE , PACK( 2 * DSIZE , 1));       // Footer
    PUT(heap + 5 * WSIZE , PACK(0,1));                  // Last Block
    heap += (2 * WSIZE);                                // bp

    if(extend_heap(CHUNKSIZE / WSIZE) == (void *)-1 ) return ;   // Extend_heap 1 MB (= 4 MB / 4 )

}

 

 

 

2) Malloc

 

Malloc : 메모리 할당

 

 

/**
 * @brief Malloc Implementation
 * Memory allocation Function
 * 
 * @param size : Size of allocation
 * @return void* : Pointer which is pointing allocated memory
 */
void * Mymalloc::mm_malloc(size_t size)
{
    size_t asize;
    size_t extendsize;
    void *bp;

    if(size == 0) return NULL;

    // Alignment - Double word ( 8bytes )
    if(size <= DSIZE) asize = 2 * DSIZE;        // IF Size is small
    else asize = (1 * DSIZE) + (((size + DSIZE -1)/DSIZE) * DSIZE);     // Other Cases

    // Finding Free block
    if((bp = find_fit(asize)) != nullptr){
        place(bp,asize);

        cout << "[ Malloc Success ] " << asize << " Bytes is allocated. " << endl;

        return bp;
    }

    // If heap size is lack -> extend_heap
    if( (bp = extend_heap(CHUNKSIZE / WSIZE)) == (void *)-1 ) return NULL;

    return mm_malloc(size);
    
}

 

 

 

3) Calloc

 

메모리 할당 + 0으로 초기화

 

 

/**
 * @brief Calloc Implementation
 * Memory allocation + initalization to zero
 * 
 * @param size : Size of allocation
 * @return void* : Pointer which is pointing allocated memory
 */
void * Mymalloc::mm_calloc(size_t size){

    void* bp;
    if((bp = mm_malloc(size)) == NULL) return NULL;
    
    // Alignment - Double word ( 8bytes )
    if(size <= DSIZE) size = DSIZE;        // IF Size is small
    else size = ((size + DSIZE -1)/DSIZE) * DSIZE;

    for(int i = 0 ; i < size/WSIZE ; ++i){
        *((int*)bp+i) = 0x0;
    }

    return bp;
}

 

Malloc을 이용하여 구현 하였다.

Malloc을 해준 뒤 값들을 0으로 초기화 해준 것이 전부이다.

 

 

 

4) Realloc

 

할당된 메모리를 재할당 해주는 함수

 

의외로 해줄 것이 많다.

주어진 사이즈와 next 블록의 할당 여부에 따라 여러가지 case들이 나온다.

자세한 Case들은 주석에 적어 두었다.

주어진 사이즈가 작으면 Decrease하는 것도 구현 하였다.

 

 

/**
 * @brief Realloc Implementation
 * Resizing allocated memory
 * 
 * @param bp : Pointer which is pointing allocated memory
 * @param size : Resizing size
 * @return void* : Pointer which is pointing reallocated memory
 */
void * Mymalloc::mm_realloc(void* bp ,size_t size){

    if( GET_ALLOC(HDBP(bp)) == 0 || size <= 0) return NULL;
    
    size_t before_size = GET_SIZE(HDBP(bp));
    size_t asize = DSIZE + ((size + (DSIZE -1)) / DSIZE) *DSIZE;

    cout << "[ Realloc Start ] Request size is " << asize <<" Bytes "  << endl;

    // Size Increasement
    if(asize > GET_SIZE(HDBP(bp))){

        // Case 1
        // Next block is free Block & Big enough
        if(GET_ALLOC(HDBP(NEXT_BLKP(bp))) == 0 && GET_SIZE(HDBP(NEXT_BLKP(bp))) >= asize - GET_SIZE(HDBP(bp))){
            coalesce(bp);
            
            cout << "[ Realloc End ] "<< before_size << " Bytes -> After " << GET_SIZE(HDBP(bp)) << " Bytes  " << endl;
            return bp;
        }

        // Case 2
        // Finding free block which is big enough
        else {
            mm_free(bp);    // Deallocate

            void * new_bp = mm_malloc(size);    // Allocate big enough memory

            for(int i = 0 ; i < (GET_SIZE(HDBP(bp)) - DSIZE)/WSIZE ; ++i){
                *((int *)new_bp+i) = *((int *)bp+i);                            // Content Copy
            }

            cout << "[ Realloc End ] "<< before_size << " Bytes -> After " << GET_SIZE(HDBP(new_bp)) << " Bytes  " << endl;

            return new_bp;
        }
    }
    // Size Decreasement
    else if(asize < GET_SIZE(HDBP(bp))){
        size_t csize = GET_SIZE(HDBP(bp))-asize;

        // Case 1
        // Remaining memory is bigger than DSIZE * 2

        if(csize >= DSIZE * 2){

            // Shrink
            PUT(HDBP(bp), PACK(asize,1));
            PUT(FTBP(bp) ,PACK(asize,1));
            
            // Remaining block
            PUT(HDBP(NEXT_BLKP(bp)) , PACK(csize,0));
            PUT(FTBP(NEXT_BLKP(bp)) , PACK(csize,0));

            coalesce(NEXT_BLKP(bp));

            cout << "[ Realloc End ] "<< before_size << " Bytes -> After " << GET_SIZE(HDBP(bp)) << " Bytes  " << endl;

            return bp;
        }
    }
}

 

 

 

5) Free

 

Deallocation 함수

 

/**
 * @brief Free Implementation
 * Free function to deallocate allocated block
 * 
 * @param bp : Pointer which is pointing allocated block
 */
void Mymalloc::mm_free(void* bp)
{
    size_t size = GET_SIZE(HDBP(bp));   // block size

    if( GET_ALLOC(HDBP(bp)) == 0 ){
        cout << "[ Free Failed ] Pointing Memory isn't allocated. ";
        return ;
    } 

    PUT(HDBP(bp),PACK(size,0));         // block header modify
    PUT(FTBP(bp),PACK(size,0));         // block footer modify
    coalesce(bp);                       // Merge with neighboring block

    cout << "[ Free Success ] " << size << " Bytes are decallocated." << endl;
}

 

 

 

 

---

이렇게 Explicit allocator를 구현 해보았다.

Malloc이 겉보기와는 다르게 이렇게 복잡한 구조를 하고 있는 줄은 몰랐다..

 

전체 코드는 github에 올려두었다.

Github 주소 : https://github.com/ohinhyuk/MCNL-Study/blob/main/%EA%B3%A0%EC%9C%A4%EB%AF%BC%EA%B5%90%EC%88%98%EB%8B%98%20%EC%8A%A4%ED%84%B0%EB%94%94/week%203/explicit_allocator.cpp

GitHub - ohinhyuk/MCNL-Study: for Study