c - カスタム malloc() 実装ヘッダーの設計

Question

C で (演習として) デバッグ目的でカスタムアロケーターを作成しようとしています。そこでは、First Fit Algorithm を使用してメモリの空きリストを保持するために単一のリンクリストを使用します。「空のメモリノード」に作成したい構造を以下に示しました。

メモリの最初の数バイトにヘッダーブロック (具体的には共用体) を書き込むにはどうすればよいですか?

これは私が使用しているユニオンです:

/*Define Header Structure for proper alignment*/
union header {
struct{
    union header* next;
    unsigned size ; /*Make it size_t*/
}s; 
double dummy_align_var;
};

-------------------------------------------------------------------------------
|Next        |Size of  |16Byte| User is concerned only about |16Byte|         |
|Free Memory |Allocated|Header| this portion  of memory      |Footer|Checksum |
|Address     |Block    |Picket| and has no knowledge of rest |Picket|         |
-------------------------------------------------------------------------------
|-------Header---------|      ^Address Returned to user
                              ^------User Requested Size-----^
^-------------Memory Obtained From The Operating System-----------------------^
*/

[編集]提供された提案に従ってブロック構造を変更しました。

score 3 · Accepted Answer

デバッグ用の malloc の場合、制御構造とユーザーデータの先頭の間、およびユーザーデータの末尾とチェックサムの間にパディングスペースを入れることを検討してください。パディングの 1 バイトはゼロバイト 0x00 にする必要があります。したがって、文字列操作は停止します。別のものを 0xFF として配置することを検討してください。固定パターンがあり、それが変化したことに気付いた場合は、何かが範囲外に踏みにじられたことがわかりますが、機密制御データが踏みにじられていない可能性が高くなります。ユーザーに割り当てられたスペースのいずれかの側に 16 バイトのパディングを使用する場合、4 バイトのゼロを適切に配置 (したがってゼロの 4 バイト整数) し、おそらく -1 には 0xFFFFFFFF を配置することになります。また、要求されたサイズを基本ブロックサイズの倍数に切り上げる可能性が高いため、ユーザーが使用しないバイトを既知の値に設定し、それらが変更されていないことを検証します。これにより、「割り当てられた長さを超える」、または割り当てられた長さをわずか数バイト超える変更が検出されますが、それ以外の場合は検出されない可能性があります。

パディングのゼロバイトの唯一の欠点は、null バイトを探すときに、割り当てられたメモリの最後で停止しない読み取り操作を容易に検出できないことです。ゼロバイトを含まないパディングを使用する代替オプションを使用することで、それらについての洞察を得ることができます。

考慮すべきもう 1 つのオプションは、ユーザーに返されるメモリから制御データを完全に分離しようとすることです。もちろん、完全に分離することは不可能ですが、少なくとも、割り当てられたブロックとは別に、割り当てのリスト (サイズとポインターを含む) を維持してください。繰り返しになりますが、これにより、貴重な制御データを、制御されていないメモリの踏みにじる操作から遠ざけることができます。誤ったポインターから完全に保護されているわけではありませんが、より適切に保護されています。(また、制御不能な書き込みを検出するために、割り当てられたスペースの周りにバッファーゾーンを提供することもできます。) ただし、この設計は質問とは著しく異なります。

'malloc()' からメモリブロックを取得すると仮定すると、おおまかに次のようになります。

void *my_malloc(size_t nbytes)
{
    size_t reqblocks = (nbytes + sizeof(header) - 1) / sizeof(header);
    size_t reqspace  = (reqblocks + 2) * sizeof(header) + 2 * sizeof(padding);
    void *space = malloc(reqspace);
    if (space == 0)
        return space;
    void *retval = (char *)space + sizeof(header) + sizeof(padding);
    header *head = space;
    head->next = ...next...;
    head->size = nbytes;
    ...set head padding to chosen value...
    ...set tail padding to chosen value...
    ...set gap between nbytes and block boundary to chosen value...
    return retval;
}

解釈が残っています...

score 2 · Accepted Answer

なぜ労働組合を利用しているのですか？フリーブロックの開始として a を使用してユーザーにstruct返すだけです。&dummy_align_var

ああ、これはデバッグ用なので、mungwall を追加することをお勧めします。ユーザー領域の両側に 16 バイトを配置し、何らかのパターン (たとえば、0xdeadbeef を 4 回繰り返す) で埋めます。これらのfree()バイトが変更されていないことを確認します。

[編集] ここにいくつかの疑似コードがあります:

struct header {
    struct header * next;
    unsigned size;
    // put mungwall here
    double user_data;
};

init()
    int blockSize = 1024;
    char * bigMem = original_malloc(blockSize);
    struct header * first = (struct header *)bigMem;
    first->next = NULL;
    first->size = blockSize - (sizeof(struct header) - sizeof(double));

score 2 · Accepted Answer

私は次のようなことをします

#define MEM_ALIGN 4 // 8 on 64b eventually

struct header {
    union aligned_header {
        struct _s {
            union aligned_header* next;
            size_t size;
        } data;
        char dummy_align_var[sizeof(struct _s) + sizeof(struct _s)%MEM_ALIGN];
    } header_data;
    char user_address;
};

と戻り&user_addressます。

score 1 · Accepted Answer

空きメモリブロックを二重リンクリストに入れることができるように、 dummy_align_varasを宣言することもできます。union header* prev

これは、解放されたブロックを前の黒と次の黒とマージする場合に、それらも解放されている場合にパフォーマンスを大幅に向上させます。

最後に、リストをサイズで並べ替えておくと、特定のリクエストに割り当てるのに最適なブロックをすばやく見つけることができ、アドレスで並べ替えると、解放されたブロックを簡単にマージできます。両方を実行する場合は、ユーザー部分を少なくとも3header*大きくして、ブロックが解放されたときに必要なポインターに収まるようにします。

アーロンが言及した境界線に加えて、解放されたバッファを同じパターンで上書きします。これにより、すでに解放されているバッファを使用しているコードを簡単に認識できます。

score 1 · Accepted Answer

私はそれが役に立つことを提案します: 数年前、私はデバッグ目的 (割り当てトレーサーなど) のために malloc() 機能をバックアップする必要がありました...そして、彼らの libstdc から FreeBSD 実装を簡単に取得するのは非常に簡単でした. FreeBSSD 5.0 または 4.x の最近のリリースを覚えているのですが、おもしろいことに、それらの機能は単純なライブラリ malloc.o モジュールに分離されていたため、このレイヤーのオーバーロードは非常に単純なコピーアンドペーストであり、実装は非常に優れていました。

あなたは本当にこのすべての仕事をするのですか？はい、確認するだけのポイントです。このソリューションが最善であるとは思いません。

score 1 · Accepted Answer

次のように、必要に応じて元のユニオンを使用できます。

union header *hdr = malloc(total_size);
void *user_ptr = hdr + 1;
char *trailer_ptr = (char *)user_ptr + user_size;

ed ブロックがそれらの共用体の配列として扱われた場合user_ptr、次のunion header開始位置に設定されます。mallocこれがユーザーに返す値です。

またtrailer_ptr、チェックサムを配置できる、ユーザーの割り当て後の最初のバイトを指すように設定します。

score 0 · Accepted Answer

0

malloc() を使用したくない場合は、sbrkを調べてください。

于 2009-11-09T13:46:50.670 に答える

c - カスタム malloc() 実装ヘッダーの設計

7 に答える 7

Related

Reference