malloc 와 free 함수 의 실현 코드 및 분석

메모리 관리 에 사용 되 는 malloc 와 free 라 는 함 수 는 C 언어 를 사용 하 는 프로그래머 에 게 익숙 할 것 입 니 다.얼마 전'간단 한 기능 을 구현 하 는 malloc'를 면접 문제 로 제시 한 IT 회사 가 있다 는 이 야 기 를 들 었 는데,마침 최근 K&R 을 복습 하고 있 는데 위 에 소개 가 있어 서 시간 을 들 여 꼼꼼 히 검토 해 봤 다.문 제 를 푸 는 것 은 부차적인 것 이기 때문에 사상 을 실현 하고 기술 을 향상 시 키 는 것 이 중요 하 다.본 고 는 주로 malloc 와 free 의 실현 방향 에 대한 소개 이 고 파란색 부분 문 자 는 개인 적 인 사고 에서 비교적 핵심 적 인 것 이 라 고 생각 합 니 다.또한 코드 에 대한 설명 은 K&R 의 해석 이 있 고 녹색 으로 밝 게 한다.
K&R 제8 장 제5 절의 실현 을 연구 하기 전에 제5 장 제4 절의 alloc/afree 실현 을 먼저 살 펴 보 자.비록 이 코드 의 주요 목적 은 주소 연산 을 보 여 주 는 것 이지 만.

alloc   
#define ALLOCSIZE 10000
static char allocbuf[ALLOCSIZE];    /*storage for alloc*/
static char *allocp = allocbuf;    /*next free position*/
char *alloc(int n)
{
    if(allocbuf+ALLOCSIZE - allocp >= n) {
        allocp += n;
        return alloc - n;
    } else
        return 0;
}
void afree(char *p)
{
    if (p >= allocbuf && p<allocbuf + ALLOCSIZE)
        allocp = p;
}

이런 간단 한 실현 의 단점:
1.메모리 자원 을 대표 하 는 allocbuf 로 서 미리 분 배 된 것 이 므 로 낭비 가 있 을 수 있 습 니 다.
2.분배 와 방출 순 서 는 창고,즉'후진 선 출'과 유사 하 며 방출 시 순서대로 이상 을 초래 할 수 있다.
이 실현 은 비록 비교적 초라 하지만,여전히 하나의 사고방식 을 제공 했다.이 두 가지 단점 을 없 앨 수 있다 면 비교적 이상 적 인 malloc/freee 를 실현 할 수 있 을 것 이다.
주소 연산 에 만 의존 하여 포 지 셔 닝 을 하 는 것 은 분배 회수 유연성 을 제한 하 는 원인 으로 이미 사용 한 부분 과 사용 하지 않 은 부분 은 반드시 특정한 주 소 를 통 해 두 개의 인접 지역 으로 나 누 어야 한다 고 요구한다.이 두 구역 이 서로 교차 할 수 있 도록 심지어 분배 되 지 않 은 주소 공간 도 포함 되 어 있 기 때문에 포인터 로 같은 메모리 공간 을 연결 하여 링크 를 만들어 야 주소 가 연속 되 지 않 는 일련의 메모리 공간 을 처리 할 수 있다.그런데 왜 빈 공간 만 연결 하고 사용 중인 공간 은 연결 하지 않 습 니까?이렇게 묻 는 것 은 그림 에서 두 사람 을 비교 할 때의 직관 에서 비롯 되 어 생각 을 하지 않 았 을 수도 있다.이것 은 매우 간단 하 다.왜냐하면 필요 하지 않 기 때문이다.전자 가 서로 연결 하 는 것 은 메모리 가 분 배 될 때 모든 빈 공간 을 옮 겨 다 니 고 free()를 사용 하여 사용 한 공간 을 회수 할 때 다시 삽입 할 수 있 도록 하 는 것 입 니 다.사용 중인 공간 에 대해 우 리 는 공간 을 분배 할 때 이미 그들의 주 소 를 알 고 있 기 때문에 회수 할 때 free()에 게 직접 알려 줄 수 있 고 malloc()처럼 옮 겨 다 니 지 않 아 도 된다.

링크 가 언급 된 이상 데이터 구조 에 대해 조금 아 는 사람 은 바로 다음 struct 를 써 서 메모리 영역 을 대표 할 수 있 습 니 다.그 중에서 다음 메모리 영역 을 가리 키 는 지침 이 포함 되 어 있 습 니 다.그러나 이 struct 의 다른 구성원 들 은 어떻게 써 야 합 니까?분 배 될 메모리 영역 으로서 크기 가 정 해 지지 않 습 니 다.이 를 struct 로 설명 하 는 구성원 변 수 는 분명 적절 하지 않 습 니 다.다른 지역 을 가리 키 는 지침 이 라 고 밝 히 면 위의 직관 적 인 표현 과 맞지 않 는 것 같다.물론 이렇게 하 는 것 도 실현 할 수 있다.이것 은 위의 그림 과 같은 두 가지 사이 에 있 고 관리 구조 와 실제 분 배 된 공간 을 분리 시 키 는 것 처럼 보인다.글 끝 에 나 는 이런 실현 방법 을 전문 적 으로 토론 할 것 이다)그래서 여 기 는 아직도 제어 구조 와 여가 공간 을 분리 시 키 지만 메모리 주소 에서 서로 인접 하여 다음 그림 의 형식 을 형성 하 는 것 이 바로 이런 특징 이다.우 리 는 제어 구조 지침 에 대한 지침 연산 을 이용 하여 대응 하 는 메모리 영역 을 찾 을 수 있다.
　　
대응 하여 제어 정 보 를 Header:

typedef long Align;/*for alignment to long boundary*/
union header { 
    struct {
        union header *ptr; /*next block if on free list*/
        unsigned size; /*size of this block*/
    } s;
    Align x;
};
typedef union header Header;

으로 정의 합 니 다.
struct 대신 유 니 온 을 사용 하 는 이 유 는 주소 정렬 을 위 한 것 입 니 다.여 기 는 롱 정렬 입 니 다.유 니 온 의 x 는 영원히 사용 되 지 않 습 니 다.
이렇게 해서 malloc 의 주요 업 무 는 바로 이러한 Header 와 그 후의 메모리 블록 에 대한 관리 이다.

malloc() 
static Header base;
static Header *freep = NULL;
void *malloc(unsigned nbytes)
{
    Header *p, *prevp;
    unsigned nunits;
    nunits = (nbytes+sizeof(Header)-1)/sizeof(Header) + 1;
    if((prevp = freep) == NULL) { /* no free list */
        base.s.ptr = freep = prevp = &base;
        base.s.size = 0;
    }
    for(p = prevp->s.ptr; ;prevp = p, p= p->s.ptr) {
        if(p->s.size >= nunits) { /* big enough */
            if (p->s.size == nunits)  /* exactly */
                prevp->s.ptr = p->s.ptr;
            else {
                p->s.size -= nunits;
                p += p->s.size;
                p->s.size = nunits;
            }
            freep = prevp;
            return (void*)(p+1);
        }
        if (p== freep) /* wrapped around free list */
            if ((p = morecore(nunits)) == NULL)
                return NULL; /* none left */
    }
}

실제 분 배 된 공간 은 Header 크기 의 정수 배 이 고 Header 크기 의 공간 을 하나 더 만들어 Header 를 배치 하 는 데 사용 합 니 다.그러나 직관 적 으로 보면 이것 은 nunits=(nbytes+sizeof(Header)-1)/sizeof(Header)+1 이 아 닙 니까?(nbytes+sizeof(Header)/sizeof(Header)+1 을 사용 하면 딱 좋 지 않 을까요?사실은 그렇지 않 습 니 다.후 자 를 사용 하면 nbytes+sizeof(Header)%sizeof(Header)=0 시 에 Header 크기 의 공간 을 하나 더 분 배 했 기 때문에 작은 괄호 에서 1 을 빼 야 요구 에 부합 할 수 있 습 니 다.
 malloc()가 처음 호출 되 었 을 때 퇴화 링크 base 를 만 들 었 습 니 다.크기 가 0 인 공간 만 있 고 자신 을 가리 키 고 있 습 니 다.freep 는 빈 링크 의 특정한 요 소 를 표시 하 는 데 사용 되 며 찾 을 때마다 변화 가 발생 할 수 있 습 니 다.중간 검색 과 배분 과정 은 기본 적 인 링크 작업 으로 남 은 링크 에 적당 한 크기 의 남 은 공간 이 존재 하지 않 을 때 morecore()를 호출 하여 더 많은 메모리 공간 을 얻 습 니 다.마지막 반환 값 은 빈 공간의 첫 번 째 주소,즉 Header 다음 주소 입 니 다.이 인 터 페 이 스 는 라 이브 러 리 함수 와 일치 합 니 다.

morecore() 
#define NALLOC 1024    /* minimum #units to request */
static Header *morecore(unsigned nu)
{
    char *cp;
    Header *up;
    if(nu < NALLOC)
        nu = NALLOC;
    cp = sbrk(nu * sizeof(Header));
    if(cp == (char *)-1)    /* no space at all*/
        return NULL;
    up = (Header *)cp;
    up->s.size = nu;
    free((void *)(up+1));
    return freep;
}

morecore()는 시스템 에서 더 많은 사용 가능 한 공간 을 신청 하고 가입 합 니 다.sbrk()를 호출 했 기 때문에 시스템 비용 이 많이 들 었 습 니 다.morecore()자체 의 호출 횟수 를 피하 기 위해 NALLOC 를 설 정 했 습 니 다.매번 신청 한 공간 이 NALLOC 보다 작 으 면 NALLOC 크기 의 공간 을 신청 하여 후속 malloc()가 매번 morecore()를 호출 하지 않 아 도 됩 니 다.sbrk()에 대해 서 는 뒤에서 소개 해 드 리 겠 습 니 다.
여기 놀 라 운 점 이 있 습 니 다.malloc()는 morecore()를 호출 했 고 morecore()는 free()를 호출 했 습 니 다!이곳 을 처음 봤 을 때 신기 할 수도 있 습 니 다.관성 적 인 사고 에 따 르 면 malloc()와 free()는 서로 분 리 된 것 같 아서 각자 맡 은 일 을 해 야 할 것 같 습 니 다.그러나 다시 한 번 생각해 보 세 요.free()는 빈 링크 를 확장 하 는 것 입 니 다.malloc()는 빈 링크 가 부족 할 때 시스템 에서 더 많은 메모리 공간 으로 신청 한 후에 도 빈 링크 의 일부분 으로 전환 시 킨 다음 에 이용 해 야 합 니 다.이렇게 해서 malloc()가 free()를 호출 하여 뒤의 일 을 완성 하 는 것 도 순리 적 이다.이 사상 에 따 르 면 뒤 에는 free()의 실현 이다.그 전에 morecore()자체 의 세부 사항 이 몇 개 있 습 니 다.
1.시스템 에 분배 할 공간 이 없 으 면 sbrk()는-1 로 되 돌아 갑 니 다.cp 는 char*형식 입 니 다.어떤 기계 에 서 는 char 기호 가 없습니다.강제 형식 변환 이 필요 합 니 다.
2.morecore()호출 된 반환 값 이 이상해 보 입 니 다.걱정 하지 마 세 요.freep 는 free()에서 수정 할 것 입 니 다.이 반환 값 을 사용 하 는 것 도 malloc()에서 의 판단,p=freep 의 재 할당 문 구 를 치밀 하 게 하기 위해 서 입 니 다.
free()

void free(void *ap)
{
    Header *bp,*p;
    bp = (Header *)ap -1; /* point to block header */
    for(p=freep;!(bp>p && bp< p->s.ptr);p=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()먼저 풀 어야 할 ap 에 대응 하 는 bp 와 남 은 링크 의 상대 적 인 위 치 를 찾 습 니 다.가장 가 까 운 이전 과 다음 남 은 공간 을 찾 거나 전체 남 은 공간의 앞 이나 뒤에 있 을 때 남 은 링크 의 첫 번 째 요 소 를 찾 습 니 다.malloc()의 배분 방식 과 free()의 회수 시 합병 방식(다음 글 에서 곧 언급 할 것)으로 인해 전체 빈 공간의 링크 가 항상 낮은 주소 에서 하나씩 올 라 가 고 최고 주소 의 빈 공간 에서 낮은 주소 의 첫 번 째 빈 공간 을 가리 키 도록 할 수 있 습 니 다.
포 지 셔 닝 후 방출 할 공간 과 인근 공간의 인접 성에 따라 통합 하 는 것,즉 해당 공간의 Header 를 수정 하 는 것 이다.두 if 를 병렬 하면 bp 가 높 은 주소 와 낮은 주소 의 빈 공간 과 결합 하거나 둘 중 하 나 를 합병 하거나 합병 하지 않 을 수 있 습 니 다.
이 세 부분 코드 를 완성 한 후(같은 원본 파일 에 넣 으 면 sbrk()는\#include가 필요 합 니 다)사용 할 수 있 습 니 다.물론 이름 과 stdlib.h 의 동명 함수 가 충돌 하여 스스로 이름 을 바 꿀 수 있 음 을 주의해 야 합 니 다.
처음으로 소스 코드 를 살 펴 보면 Header 의 구조 와 정렬 충전,공간의 정리,링크 의 조작 과 초기 화(경계 상황),malloc()대 free()의 호출,malloc()와 free()가 몰래 보장 하 는 링크 주소 의 질서 등 이 생각 하지 못 했 을 수도 있 습 니 다.또한 앞에서 언급 한 두 가지 문 제 를 동봉 하고 보충 문제 에 대한 간단 한 사고 도 있다.
1.Header 는 남 은 공간 과 분리 되 고 Header 에는 남 은 공간 을 가리 키 는 지침 이 포함 되 어 있 습 니 다.
이렇게 하면 반드시 안 되 는 것 은 아니 며,상응하는 알고리즘 은 바 꿔 야 한다.또한,Header 와 남 은 공간 이 더 이상 인접 하지 않 기 때문에 sbrk()가 얻 은 공간 도 Header 의 부분 을 포함해 야 하 며 메모리 의 분 포 는 더욱 번 거 로 울 수 있 습 니 다.물론 이것 은 좋 은 점 을 가 져 올 수 있다.즉,다른 데이터 구조 로 링크 를 관리 하 는 것 이다.예 를 들 어 크기 에 따라 hash 를 하면 더욱 빨리 찾 을 수 있다.
2.sbrk()에 대하 여
sbrk()도 라 이브 러 리 함수 입 니 다.스 택 으로 쌓 이 는 방향 을 증가 시 킬 수 있 습 니 다.구체 적 으로 는 brk(),sbrk()용법 에 대한 상세 한 설명 을 참고 할 수 있 습 니 다.
3.개선 할 수 있 는 방법
남 은 공간 을 찾 는 것 은 선형 이 고 검색 과정 은 메모리 배분 에서 순환 의 첫 번 째 적응 알고리즘 으로 볼 수 있 으 며 어떤 경우 에는 느 릴 수 있 습 니 다.만약 에 hash 표 와 같은 데이터 구 조 를 다시 만 들 면 서로 다른 크기 의 공간 을 색인 하면 그 자 체 를 빨리 찾 을 수 있 고 알고리즘 을 실현 할 수 있 습 니 다.예 를 들 어 가장 좋 은 일치 등 입 니 다.그러나 검색 이 빨 라 지 는 대 가 는 이 색인 을 수정 하 는 데 추가 시간 이 걸 리 므 로 저울질 해 야 한 다 는 것 이다.
morecore()의 최소 분배 공간 은 매크로 정의 로 실제 사용 에서 매개 변수 로 전달 할 수 있 으 며 필요 에 따라 최소 분배 하한 선 을 설정 할 수 있 습 니 다.