3

私は自分のメモリ割り当てプログラムを (malloc を使用せずに) 書いていますが、今は free 関数 (私のコードでは asfree) に固執しています。割り当ての機能はすべて揃っていると思いますが、唯一の問題は無料の機能にあります。以下のコードを実行すると、32 個のブロックを割り当てることができます。各ブロックのサイズは 48 + 16 (ヘッダーのサイズ) です。では、それらを割り当てた直後にそれらをすべて解放/解放するにはどうすればよいですか? 私の無料関数を見て、正しい方向に向けてもらえますか?

PS: これは学習用です。構造体、リンクリスト、メモリ割り当てについて頭を悩ませようとしています。前もって感謝します。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define BUFFER_SIZE 2048

typedef struct blk_struct
{
    size_t  size_blk;
    struct  blk_struct *next;
    char    data[0];
}blk_struct;

struct blk_struct *first = NULL;
static char buffer[BUFFER_SIZE];

void *asalloc(size_t size)
{
    int nunits = (size + sizeof(blk_struct));
    static int val = 1;

    blk_struct *block, *current;

    //locate position for block
    if(first == NULL)
    {
        block = (blk_struct *)&buffer[0];

        // Sanity check size.
        if(nunits > BUFFER_SIZE)
            return NULL;

        // Initialise structure contents.
        block->size_blk = size;
        block->next     = NULL;

        // Add to linked list.
        first = block;

        // Give user their pointer.
        return block->data;
    }
    //create a free list and search for a free block
    for(current = first; current != NULL; current = current->next)
    {
        // If this element is the last element.
        if(current->next == NULL)
        {
            block = (blk_struct *) (current->data + current->size_blk);

            // Check we have space left to do this allocation
             if((blk_struct *) &block->data[size] >
                     (blk_struct *) &buffer[BUFFER_SIZE])
             {
                 printf("No more space\n");
                 return NULL;
             }

            // Initialise structure contents.
            block->size_blk = size;
            block->next     = NULL;

            // Add to linked list.
            current->next   = block;
            // Give user their pointer.
            return block->data;
        }
    }
    printf("List Error\n");
    return NULL;
}

// 'Free' function. blk_ptr = pointer to the block of memory to be released
void asfree(void *blk_ptr)
{
    struct blk_struct *ptr = first;
    struct blk_struct *tmp = NULL;

    while(ptr != NULL)
    {
        if(ptr == blk_ptr)
        {
            printf("Found your block\n");
            free(blk_ptr);
            break;
        }
        tmp = ptr;
        ptr = ptr->next;
    }
}

// Requests fixed size pointers
int test_asalloc(void)
{
    void *ptr = NULL;
    int size = 48;
    int i = 1;
    int total = 0;

    do
    {
        ptr = asalloc(size);

        if(ptr != NULL)
        {
            memset(ptr, 0xff, size);
            printf("Pointer %d = %p%s", i, ptr, (i % 4 != 0) ? ", " : "\n");
            // each header needs 16 bytes: (sizeof(blk_struct))
            total += (size + sizeof(blk_struct));
            i++;
        }
        asfree(ptr); // *** <--- Calls the 'free' function ***
    }
    while(ptr != NULL);
    printf("%d expected %zu\nTotal size: %d\n", i - 1,
            BUFFER_SIZE / (size + sizeof(blk_struct)), total);
}

int main(void)
{
    test_asalloc();
    return 0;
}
4

1 に答える 1

2

あなたの asfree にはいくつか問題があります。

sizeof(blk_struct)ブロックの頭を探すときは引く必要があります。ユーザーが解放したい割り当てられたデータはヘッダーのすぐ後ろにあり、ヘッダーではなくそのデータへのポインターがあります。

2 番目の問題は、ヘッダーを取得したときに何をするかです。データだけで無料通話はできません。ヘッダーに何らかのフラグを設定し、ブロックをフリーとしてマークする必要があります。次にブロックを割り当てようとするときは、最後に新しいブロックを作成するだけでなく、空いているブロックを再利用できる必要があります。大きな空きブロックを2つの小さなブロックに分割できるのも良いです。フラグメンテーションを回避するには、隣接する空きブロックを 1 つ大きなブロックにマージする必要があります。

現在、私は学校のプロジェクトとして OS を作成しています。次のように機能するシンプルなアロケーターを使用することをお勧めします。

  • メモリのブロックには、隣接ブロックへのリンクと空きフラグを含むヘッダーがあります。
  • 最初に、メモリ全体をカバーする free フラグを持つ 1 つの大きなブロックがあります。
  • malloc が呼び出されると、ブロックが最初から最後まで検索されます。十分な大きさのブロックが見つかると、2 つに分割されます (割り当てられた 1 つと無料のリマインダー)。割り当てられたブロック データへのポインタが返されます。
  • free が呼び出されると、一致するブロックが free としてマークされます。隣接ブロックも空いている場合、それらはマージされます。

これは、断片化やメモリの損失なしに malloc と free を実行できる基本だと思います。

ヘッダーとフッターの構造は次のようになります。

// Header of a heap block
typedef struct {
    // Size of the block including header and footer
    size_t size;

    // Indication of a free block
    bool free;

    // A magic value to detect overwrite of heap header.
    uint32_t magic;

} heap_block_head_t;


// Footer of a heap block
typedef struct {
    // A magic value to detect overwrite of heap footer.
    uint32_t magic;

    // Size of the block
    size_t size;

} heap_block_foot_t;

上記のようなヘッダーとフッターを持つブロックでいっぱいのヒープは、リンクされたリストによく似ています。ブロックは隣接するブロックを明示的に記述しませんが、ブロックがそこにある限り、簡単に見つけることができます。1 つのヘッダーの位置がある場合、その位置にブロック サイズを追加すると、次のブロックのヘッダーの位置があります。

// Get next block
heap_block_head_t *current = ....
heap_block_head_t *next = (heap_block_head_t*)(((void*) current) + current->size);

// Get previous block
heap_block_head_t *current = ....
heap_block_foot_t *prev_foot = (heap_block_foot_t*)(((void*) current) - sizeof(heap_block_foot_t));
heap_block_head_t *prev = (heap_block_head_t*)(((void*) prev_foot) + sizeof(heap_block_foot_t) - prev_foot->size);

// Not sure if this is correct. I just wanted to illustrate the idea behind.
// Some extra check for heap start and end are needed

お役に立てれば。

于 2012-12-05T00:15:49.857 に答える