[C++][Malloc] Implicit allocator 구조 및 구현

출처 : https://www.crunchbase.com/organization/allocator

 

 

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

 

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

 

 

Dynamic Memory Allocation 이란??

 

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

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

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

 

 

사용 이유

 

: 효율적인 메모리 관리

 

 

Block 이란?

메모리를 관리하는 단위

 

 

< Block 구성 > ( Implicit allocator )

 

[Header , Payload , Padding , Footer]

 

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

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

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

 

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

 

 

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

 

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

여기에서는 Java / Lisp 에서 사용하는 Implicit Allocator에 대해서 배워 보겠다.

 

 

 

Implicit allocator

 

 

@ 순차적으로 모든 블록들을 검사하는 선형적인 방법

@ Free가 자동으로 진행 되기 때문에 garbage collection이라고도 불림

@ Java / Lisp 등 high-level 언어에서 사용

 

 

※ Java 에서는 C언어에서 처럼 일일이 할당된 메모리를 직접 Free를 통해 해제 해줄 필요가 없는데,

그 이유는 Java에는 garbage collection이 있어서 자동으로 불필요한 메모리를 해제해주기 때문이다.

 

 

 

가용 블록을 찾는 방법

 

First-fit : 할당 가능한 가용 블록을 앞에서 부터 찾는다.

Next-fit : 할당 요청된 메모리에 알맞은 메모리를 줬다면 그 다음 메모리 요청 때는 그 위치에서 부터 시작하여 찾는다.

Best-fit : 할당 가능한 가용 블록 중 가장 작은 블록을 할당해 준다.

 

 

Next-fit 이 가장 성능이 좋다.

하지만 쉬운 이해를 위해 First-fit으로 구현을 해보았다.

 

 

 

Heap 구조

출처 :&nbsp;https://velog.io/@emplam27/CS-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-%EB%A9%94%EB%AA%A8%EB%A6%AC-%EB%8F%99%EC%A0%81%ED%95%A0%EB%8B%B9-Implicit-Explicit-Segregated-list-Allocator

 

 

가용 블록과 할당 블록이 함께 존재하는 Implicit allocator의 heap공간이다.

 

 

 

---

 

Implicit Allocator 구현

 

C++를 통해 구현하였다.

 

 

 

맴버 변수

 

char* heap ;        // Start point of Heap                      
char* brk;          // End point of Heap
char* max_addr;     // Max Address of Heap

 

 

 

매크로

 

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

// size + alloc bit
#define PACK(size, alloc) ((size) | (alloc))

// GET , SET Function block pointer
#define GET(p) (*(unsigned int *)(p))
#define PUT(p,val) (*(unsigned int*)(p) = (val))

#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)


/**
 * @brief Macros for Block
 */

#define HDRP(bp) ((char *)(bp) - WSIZE)
#define FTRP(bp) ((char *)(bp) + (GET_SIZE(HDRP(bp))) - DSIZE )

#define NEXT_BLKP(bp) ((char*)(bp) + GET_SIZE(HDRP(bp)))
#define PREV_BLRP(bp) ((char*)(bp) - GET_SIZE( (char *)(bp) - DSIZE ))

 

 

매크로가 정말 많다.

 

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

 

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

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

 

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

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

 

 

 

---

서브 함수들

 

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
 */
char* Mymalloc::extend_heap (size_t words)
{
    char *bp;
    size_t size;

    size = (words % 2) ? (words +1) * WSIZE : words * WSIZE;

    if((long)(bp = mem_sbrk(size)) == -1) return NULL;

    PUT(HDRP(bp),PACK(size , 0));
    PUT(FTRP(bp) ,PACK(size , 0));
    PUT(HDRP(NEXT_BLKP(bp)) , PACK(0,1));

    return coalesce(bp);
}



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

    if( (incr < 0) || ( (brk + incr) > max_addr) ){
        perror("mem_sbrk failed.");
        return (char *)-1;
    }
    
    brk += incr;
    return (char*)old_brk;
}

 

 

Coalesce 함수

 

 

 

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

 

/**
 * @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
 */
char * Mymalloc::coalesce(char *bp){
    
    size_t size = GET_SIZE(HDRP(bp));
    size_t prev_alloc = GET_ALLOC(HDRP(PREV_BLRP(bp)));
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));

    if(prev_alloc && next_alloc){
        return bp;
    }

    else if( !prev_alloc  && next_alloc){
        size += GET_SIZE(HDRP(PREV_BLRP(bp)));
        PUT(HDRP(PREV_BLRP(bp)),PACK(size , 0));
        PUT(FTRP(bp), PACK(size,0));

        bp = PREV_BLRP(bp);
    }

    else if(prev_alloc && !next_alloc ) {
        size += GET_SIZE( HDRP(NEXT_BLKP(bp)));
        PUT(HDRP(bp), PACK(size,0));
        PUT(FTRP(bp) , PACK(size,0));

    }

    else{
        size += GET_SIZE(HDRP(PREV_BLRP(bp))) + GET_SIZE(HDRP(NEXT_BLKP(bp)));
        PUT( HDRP(PREV_BLRP(bp)) , PACK(size , 0));
        PUT( FTRP(NEXT_BLKP(bp)), PACK(size,0));

        bp = PREV_BLRP(bp);
    }

    return bp;
}

 

 

주석 참고!!

 

 

 

Find_Fit , Place 함수

 

 

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

 

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

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

 

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

    for(bp = heap ; GET_SIZE(HDRP(bp)) > 0; bp += GET_SIZE(HDRP(bp)) ){
        if(!GET_ALLOC(HDRP(bp)) && GET_SIZE(HDRP(bp)) >= asize) return bp;
    }

    return NULL;
}


/**
 * @brief The function that put the remaining block back in the heap 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(char *bp, size_t asize){

    size_t csize = GET_SIZE(HDRP(bp));

    if((csize - asize) >= 2 * DSIZE){
        PUT(HDRP(bp) , PACK(asize , 1));
        PUT(FTRP(bp) , PACK(asize , 1));
        
        PUT(HDRP(NEXT_BLKP(bp)),PACK(csize-asize , 0));
        PUT(FTRP(NEXT_BLKP(bp)) , PACK(csize-asize , 0));
    }   
    else{
        PUT(HDRP(bp) , PACK(csize , 1));
        PUT(FTRP(bp) , PACK(csize, 1));
    }

}

 

 

 

---

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

 

 

 

 

1) init 초기화

 

Malloc을 위한 준비

 

/**
 * @brief Heap initalization for allocation
 */
void Mymalloc::mm_init(){
    if( (heap = (char *)mem_sbrk(4 * WSIZE)) == (char* )-1 ) return ;

    PUT(heap , 0);                              // Padding
    PUT(heap + 1 * WSIZE , PACK(DSIZE , 1));    // Header
    PUT(heap + 2 * WSIZE , PACK(DSIZE , 1));    // Footer
    PUT(heap + 3 * WSIZE , PACK(0,1));          // Last Block
    heap += (2 * WSIZE);                       

    if(extend_heap(CHUNKSIZE / WSIZE) == NULL) return ;

    return ;
}

 

 

2) Malloc

 

Malloc : 메모리 할당

 

/**
 * @brief Malloc Implementation
 * 
 * @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;
    char *bp;

    if(size == 0) return NULL;

    // Alignment - Double word ( 8bytes )
    if(size <= DSIZE) asize = 2 * DSIZE;
    else asize = DSIZE + ((size + DSIZE -1) / DSIZE) * DSIZE ;
    
    // Finding Free block
    if((bp = find_fit(asize)) != NULL){
        
        place(bp,asize);
        return bp;
    }

    // If heap size is lack -> extend_heap
    if( (bp = extend_heap(asize / WSIZE)) == NULL) return NULL;
    
    place(bp,asize);
    return (void *)bp;
    
}

 

 

3) Calloc

 

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

 

/**
 * @brief Calloc implementation
 * 
 * @param size : Calloc Size
 * @return void* : Pointer which is pointing Callocated memory
 */
void* Mymalloc::mm_calloc(size_t size)
{

    // Malloc
    char* bp;
    if( (bp = (char *)mm_malloc(size)) == NULL) return NULL;

    
    if(size <= DSIZE) size = DSIZE;
    else size = ((size + (DSIZE-1)) / DSIZE) * DSIZE;
    
    // Initialization to zero
    for(int i = 0 ; i < size ; ++i){
        *(bp+i) = (char)0x0;
    }

    return bp;
}

 

 

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

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

 

 

 

4) Realloc

 

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

 

의외로 해줄 것이 많다.

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

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

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

 

 

/**
 * @brief Realloc implementation
 * 
 * @param bp : Pointer which is pointing allocated memory
 * @param size : Realloc Size
 * @return void* : Pointer which is pointing reallocated memory
 */
void * Mymalloc::mm_realloc(void* bp ,size_t size){
    
    // Can't reallocate
    if(GET_ALLOC(HDRP(bp)) == 0 || size <= 0) return NULL;

    size_t asize = DSIZE + ((size + (DSIZE - 1)) / DSIZE) * DSIZE;
    size_t before_asize = GET_SIZE(HDRP(bp));

    // Size Increasement
    if( asize > before_asize ){
        
        // Case 1
        // Next block is free Block & big enough
        if( GET_ALLOC(HDRP(NEXT_BLKP(bp))) == 0 && (GET_SIZE(HDRP(NEXT_BLKP(bp))) + before_asize >= asize) ){
            size_t next_size = GET_SIZE(HDRP(NEXT_BLKP(bp)));
            
            if(next_size + before_asize > asize + DSIZE){
                PUT(HDRP(bp) , PACK(asize , 1));
                PUT(FTRP(bp) , PACK(asize , 1));

                PUT(HDRP(NEXT_BLKP(bp)) ,PACK( (next_size + before_asize - asize),0 ) );
                PUT(FTRP(NEXT_BLKP(bp)) , PACK( (next_size + before_asize - asize),0 ) );

                coalesce(NEXT_BLKP(bp));
                
                return bp;
            }
            else{
                PUT(HDRP(bp) , PACK( (next_size + before_asize) , 1));
                PUT(FTRP(bp) , PACK( (next_size + before_asize) , 1));

                return bp;
            }
        }

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

            new_bp = (char *)mm_malloc(size);

            for(int i = 0 ; i < ( asize - DSIZE) ; ++i){
                *(new_bp +i) = *((char*)bp+i);
            }

            return new_bp;
        }
    }
    // Size Decreasement
    else if(asize < before_asize){
        
        size_t next_size = before_asize - asize;

        // Case 1
        // Remaining memory is bigger than DSIZE * 2
        
        if(before_asize - asize > DSIZE){

            PUT(HDRP(bp) , PACK(asize , 1));
            PUT(FTRP(bp) , PACK(asize , 1));

            PUT(HDRP(NEXT_BLKP(bp)), PACK(next_size , 0));
            PUT(FTRP(NEXT_BLKP(bp)) , PACK(next_size , 0));

            coalesce(NEXT_BLKP(bp));
            return bp;
        }
    }
}

 

 

5) Free

 

Deallocation 함수

 

 

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

    PUT(HDRP(bp),PACK(size,0));
    PUT(FTRP(bp),PACK(size,0));
    coalesce((char *)bp);

}

 

 

---

 

여기까지가 Implicit allocator 구현이었다.

전체 코드는 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/Implicit_allocator.cpp