malloc 구현?

malloc 구현?

저는 를 하고 있습니다.malloc그리고.freeC의 경우, 메모리를 재사용하는 방법을 잘 모르겠습니다.금을 있습니다.struct다음과 같이 보입니다.

typedef struct _mem_dictionary {
    void *addr;
    size_t size;
    int freed;
} mem_dictionary;

나의malloc다음과 같습니다.

void *malloc(size_t size) {
    void *return_ptr = sbrk(size);
    if (dictionary == NULL) 
        dictionary = sbrk(1024 * sizeof(mem_dictionary));

    dictionary[dictionary_ct].addr = return_ptr;
    dictionary[dictionary_ct].size = size;
    dictionary[dictionary_ct].freed = 1;
    dictionary_ct++;

    return return_ptr;
}

내가 메모리를 비울 때, 나는 그냥 주소를 다음과 같이 표시할 것입니다.0(그것은 그것이 무료라는 것을 나타낼 수 있습니다.의에malloc 하고, loop에 대해서는 에서 한 을 하여 을 한 0그 주소에 메모리를 할당합니다.저는 이것을 어떻게 구현해야 할지 좀 혼란스럽습니다.

가장 쉬운 방법은 링크된 무료 블록 목록을 보관하는 것입니다.malloc 있지 시킬 수 만큼 큰 이 을 할 합니다 하여 을 합니다 하여 을 이 있거나 수 어한을을수는우을다나우다을f는uln이수을어eos나tf을krh한sbrk운영 체제에서 약간의 메모리를 할당합니다.free의 목록에 . , 를 에 만 만 에 를 .보너스로 연속된 자유 블록을 병합하고 반환할 블록을 선택하는 정책을 변경할 수 있습니다(첫 번째 적합, 최상 적합, ...).블록이 요청보다 클 경우 블록을 분할하도록 선택할 수도 있습니다.

일부 샘플 구현(테스트되지 않았으며 나사산이 안전하지 않은 것은 분명합니다. 사용자의 위험을 무릅쓰고 사용):

typedef struct free_block {
    size_t size;
    struct free_block* next;
} free_block;

static free_block free_block_list_head = { 0, 0 };
static const size_t overhead = sizeof(size_t);
static const size_t align_to = 16;

void* malloc(size_t size) {
    size = (size + sizeof(size_t) + (align_to - 1)) & ~ (align_to - 1);
    free_block* block = free_block_list_head.next;
    free_block** head = &(free_block_list_head.next);
    while (block != 0) {
        if (block->size >= size) {
            *head = block->next;
            return ((char*)block) + sizeof(size_t);
        }
        head = &(block->next);
        block = block->next;
    }

    block = (free_block*)sbrk(size);
    block->size = size;

    return ((char*)block) + sizeof(size_t);
}

void free(void* ptr) {
    free_block* block = (free_block*)(((char*)ptr) - sizeof(size_t));
    block->next = free_block_list_head.next;
    free_block_list_head.next = block;
}

:(n + align_to - 1) & ~ (align_to - 1)를 둥글게 하는 입니다.n장운지지f의 가장 가까운 align_to보다 더 큰n. 이것은 다음 경우에만 작동합니다.align_to는 2의 거듭제곱이고 숫자의 이진법 표현에 의존합니다.

align_to이고, 따라서 π 2π π, π π π,align_to - 1는 모든 최하위 비트 집합을 갖습니다(즉).align_to...010...0의 형태이며,align_to - 1입니다.000...001...1)을 이 말입니다.~ (align_to - 1)는 모든 하이 비트가 설정되어 있고 로우 비트가 설정되어 있지 않습니다.형식을 갖추었습니다111...110...0). 그래서.x & ~ (align_to - 1)의든를로우 0됩니다의 모든 로우 합니다.x을운로다장다ef고ot의 배수로 반올림합니다.align_to.

마지막으로 추가하기align_to - 1sizeΔ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ align_to(그렇지 않으면)size미의입니다의 입니다.align_to는을 얻고 싶습니다.size).

설정하고 싶지 않으실 겁니다.size -- 사용하려면 해당 합니다.0으로 가는 사전 항목 필드 -- 다시 사용하려면 해당 정보가 필요합니다.신을 설정하고, setfreed=1블록이 자유로워질 때만 가능합니다.

Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δsbrk()더 .당신은 단지 당신이 필요합니다.for충분히 큰 여유 블록을 검색하는 loop:

typedef struct _mem_dictionary
{
    void *addr;
    size_t size;
    int freed;
} mem_dictionary;


void *malloc(size_t size)
{
     void *return_ptr = NULL;
     int i;

     if (dictionary == NULL) {
         dictionary = sbrk(1024 * sizeof(mem_dictionary));
         memset(dictionary, 0, 1024 * sizeof(mem_dictionary));
     }

     for (i = 0; i < dictionary_ct; i++)
         if (dictionary[i].size >= size
          && dictionary[i].freed)
     {
         dictionary[i].freed = 0;
         return dictionary[i].addr;
     }

     return_ptr = sbrk(size);

     dictionary[dictionary_ct].addr = return_ptr;
     dictionary[dictionary_ct].size = size;
     dictionary[dictionary_ct].freed = 0;
     dictionary_ct++;

     return return_ptr;
}

void free(void *ptr)
{
    int i;

    if (!dictionary)
        return;

    for (i = 0; i < dictionary_ct; i++ )
    {
        if (dictionary[i].addr == ptr)
        {
            dictionary[i].freed = 1;
            return;
        }
    }
}

이것은 대단한 것이 아닙니다.malloc()실행.사실 대부분은malloc/free구현들은 malloc에 의해 반환되는 각 블록에 대해 작은 헤더를 할당할 것입니다.예를 들어 헤더는 반환된 포인터보다 8바이트 적은 주소에서 시작할 수 있습니다.해당 바이트에는 에 대한 포인터를 저장할 수 있습니다.mem_dictionary블록을 소유하는 항목입니다.게의을 O(N)수다할면다ne O(을 피합니다.freeO(N)의 O 수 . O(N)은 malloc()자유 블록의 우선순위 대기열을 구현함으로써.블록 크기를 인덱스로 사용하는 이항 힙을 사용하는 것을 고려해 보십시오.

나는 실뱅의 응답에서 코드를 빌리고 있습니다.그는 오버헤드를 계산하는 free_block*ini의 크기를 계산하는 것을 놓친 것 같습니다.

전반적으로 코드는 할당된 메모리에 이 free_block을 헤더로 붙여서 작동합니다. 1.사용자가 malloc을 호출하면 malloc은 이 헤더 바로 뒤에 있는 페이로드의 주소를 반환합니다. 2. free를 호출하면 블록에 대한 헤더의 시작 주소가 계산되고(블록 주소에서 헤더 크기를 빼서) free 블록 풀에 추가됩니다.

typedef struct free_block {
    size_t size;
    struct free_block* next;
} free_block;

static free_block free_block_list_head = { 0, 0 };

// static const size_t overhead = sizeof(size_t);

static const size_t align_to = 16;

void* malloc(size_t size) {
    size = (size + sizeof(free_block) + (align_to - 1)) & ~ (align_to - 1);
    free_block* block = free_block_list_head.next;
    free_block** head = &(free_block_list_head.next);
    while (block != 0) {
        if (block->size >= size) {
            *head = block->next;
            return ((char*)block) + sizeof(free_block);
        }
        head = &(block->next);
        block = block->next;
    }

    block = (free_block*)sbrk(size);
    block->size = size;

    return ((char*)block) + sizeof(free_block);
}

void free(void* ptr) {
    free_block* block = (free_block*)(((char*)ptr) - sizeof(free_block ));
    block->next = free_block_list_head.next;
    free_block_list_head.next = block;
}

언급URL : https://stackoverflow.com/questions/5422061/malloc-implementation