malloc()에 대해서

 

C Programming Language에서 후반부에서는 Memory 관리 파트가 나옵니다.

 

이 부분에서, 원시형태의 Malloc을 볼 수가 있습니다.

(현재는 이것보다 훨신 복잡할태지만요)

 

아래 코드를 보시죠.

#include <stdio.h>

typedef long Align;

union header{ //memory block
    struct {    	
        union header *ptr; //next memory block
        unsigned size;     //current memory block's size
    } s;
    //Align을 위해서 존재하는 dummy
    Align x;
};
typedef union header Header;

malloc은 header라는 Union을 사용해서 free List를 관리합니다. 

 

header를 보면, union을 사용하는 점을 확인할 수 있습니다. 

 

책에서는 Align에 대해서 "각 header를 최악의 경우에 경계에서 정렬 되도록 할뿐이다" 라고 되어있습니다.

 

Union같은 경우 가장 Size가 큰 Data type의 크기로 Size가 고정됩니다.

 

즉, header Pointer가 아무것도 할당되지 않은 경우를 대비한 데이터 구조라고 예상해 볼 수 있습니다.

(이부분은 책을 아무리봐도 저도 잘 이해가 되질 않더라구요)

//empty list to get started
static Header base; 
//malloc이 호출되었을 때 처음으로 확인할 free영역을 가리키는 포인터
static Header *freep = NULL;

void *malloc(unsigned nbytes)
{
    Header *p, *prevp;
    Header *morecore(unsigned);
    unsigned nunits;

    //nbytes를 요청하면 nbytes + 헤더의 크기
    //sizeof(Header) = 16
    nunits = (nbytes + sizeof(Header) -1)/sizeof(Header) + 1;
    //prevp에 freep를 동기화시켜줍니다.
    //freep가 아직 NULL인경우
    //base의 ptr는 base자신을, base의 size는 0으로 초기화
    if ((prevp = freep) == NULL){ 
        base.s.ptr = freep = prevp = &base;
        base.s.size = 0;        
    }
    
    //현재 p를 previous p의 ptr에 할당
    for (p = prevp->s.ptr; ;prevp = p, p = p->s.ptr){
    	//현재 p의 size가 충분한 경우
        if (p->s.size >= nunits){
            //요구한 size랑 현재p의 size가 완전 동일한 경우
            if (p->s.size == nunits){
                prevp->s.ptr = p->s.ptr;
            } else {
            //요구한 size가 현재p의 size보단 작은 경우           
            p->s.size -= nunits;
            p += p->s.size;
            p->s.size = nunits;
            }
            freep = prevp;
            return (void *)(p+1);
        } 
        if(p == freep){
            if ((p = morecore(nunits))==NULL){
                return NULL;
            }
        }
    }
};

mallco의 동작을 살펴보면

1. 요청한 nbytes를 메모리 요청하기에 적절한 수(nunits)로 변환해준다.

 

2. Local prevp를 freep에 복사(주소복사)시킵니다. 그리고 freep의 상태에 따라서 base를 조정해줍니다.

 

3. p는 prevp의 next memory block이 됩니다.

 

4. p의 size를 확인하고, p의 size가 요청한 nunits와 비교합니다.

4_1 사이즈가 일치하면 prevp의 next block을 p의 next block으로 갈아줍니다.

4_2 사이즈가 충분하면 p의 s를 줄이고, p의 size만큼 옮깁니다(pointer의 정수연산)

 

5. static freep의 정보를 Update해줍니다.

 

6. allocation이 완료된 위치(p+1)을 반환합니다.

 

위 과정을 그림으로 어떻게던 그려보면, 아래와 같습니다.

(4_2 Case를 바탕으로 그려봤습니다. p+p->s.ptr을 임의로 p'라고 표기했습니다)

추상화해본 malloc의 동작

이때, run time중에 sizeof(Header) = 16임을 알 수 있습니다.

 

때문에 만약에 40bytes를 요청할 경우

 

(40+16-1)/16 + 1 = 4가 나오며, 4개의 header에 해당하는 만큼 memory확보하게 됩니다.

(1을 요청하면 16/16 + 1, 0을 요청하면 15/16 + 1이 되는것을 알 수 있습니다. 16단위로 내림을 위한 수식이라고 할 수 있습니다)

 

이후 한개는 고정적으로 memory block을 저장하는 header에 사용되고, 나머지 3*16 = 48 만큼의 bytes가 void pointer 형태로 반환되는 것으로 예상됩니다.

 

결국, malloc내에서는 이미 접근이 허락된 memory의 정보를 가지고 malloc이 진행한다고 할 수 있습니다.

 

이때 접근이 허락된 메모리의 정보는 morecore 명령을 통해서 확보됩니다.

(p->s.ptr이 freep를 가리키면, 더이상 허락된 memory 정보가 없는 상황이 됩니다)

#define NALLOC 1024
static Header *morecore(unsigned nu)
{
    char *cp, *sbrk(int);
    Header *up;
    if (nu < NALLOC){
        nu = NALLOC;
    };
    cp = sbrk(nu*sizeof(Header));
    if (cp == (char *)-1){
        return NULL;
    };
    up = (Header *)cp;
    up->s.size = nu;
    free((void *)(up +1));
    return freep;
};

morecore 내에서는 필요한 size를 확인하고, 최소 1024*sizeof(header)단위로 허락된 메모리정보를 확보하는것을 확인할 수 있습니다.

 

중간에 sbrk라는 함수가 해당 동작은 진행하며, linux의 저수준 프로그램이라고 보시면 됩니다.

https://en.wikipedia.org/wiki/Sbrk

sbrk - Wikipedia

 

free함수를 이용하면 freep의 변경이 발생합니다.

void free(void *ap){
    Header *bp, *p;

    bp = (Header *)ap - 1; // point to block header
    //p < bp < p->s.ptr가 아닐때까지 반복
    // ==> p > bp or p->s.ptr < bp
    for(p = freep; !(bp>p && bp<p->s.ptr; p -> s.ptr)){
        //p->s.ptr 이 p보다 작거나 같을때
        //and (bp > p 또는 bp < p->s.ptr)
        if (p>=p->s.ptr && (bp>p || bp<p->s.ptr)){
            break; //freed block at start or end of arena
        }
    }

    if (bp + bp->s.size == p->s.ptr){//join to upper nbr
        bp->s.size += p->s.ptr->s.size
        bp->s.ptr = p->s.ptr->s.ptr;
    } else {
        bp->s.ptr = p->s.ptr;
    }
    if (p + p->s.size == bp){//join to lower nbr
        p->s.size += bp->s.size;
        p->s.ptr = bp->s.ptr;        
    } else {
        p->s.ptr = bp;
    }
    freep = p;
}

free 함수 내부에서는 freep의 병합이 있는것을 확인할 수 있습니다.

 

bp(base pointer?)의 위치를 현재 freep를 이용해서 결정하고

 

이 bp를 가지고 주변 pointer들을 병합한 다음

 

이 bp를 p에다가 할당하고, 이 p를가지고 freep를 변경하게 됩니다.