標準ライブラリのみを使用してアライメントされたメモリを割り当てる方法は?

元の回答

{
    void *mem = malloc(1024+16);
    void *ptr = ((char *)mem+16) & ~ 0x0F;
    memset_16aligned(ptr, 0, 1024);
    free(mem);
}

正解

{
    void *mem = malloc(1024+15);
    void *ptr = ((uintptr_t)mem+15) & ~ (uintptr_t)0x0F;
    memset_16aligned(ptr, 0, 1024);
    free(mem);
}

要求に応じた説明

最初のステップは、万が一に備えて十分な予備スペースを割り当てることです。メモリは 16 バイトにアラインされている必要があるため (つまり、先頭のバイト アドレスは 16 の倍数である必要があります)、16 バイトを追加することで十分なスペースが確保されます。最初の 16 バイトのどこかに、16 バイトにアラインされたポインターがあります。 ( malloc() に注意してください any に対して十分に整列されたポインタを返すことになっています 目的。ただし、'any' の意味は、主に基本的な型のようなものです — longdoublelong doublelong long 、およびオブジェクトへのポインターと関数へのポインター。グラフィックス システムで遊ぶなど、より専門的なことを行う場合、システムの残りの部分よりも厳密な調整が必要になる可能性があります。そのため、このような質問と回答があります。)

次のステップは、void ポインターを char ポインターに変換することです。 GCC にもかかわらず、void ポインターでポインター演算を行うことは想定されていません (また、GCC には、それを悪用した場合に通知する警告オプションがあります)。次に、開始ポインターに 16 を追加します。 malloc() とします。 ありえないほどアラインされていないポインター 0x800001 を返しました。 16 を追加すると、0x800011 が得られます。ここで、16 バイト境界に切り捨てたいので、最後の 4 ビットを 0 にリセットします。0x0F は最後の 4 ビットを 1 に設定します。したがって、~0x0F 最後の 4 つを除くすべてのビットが 1 に設定されています。それに 0x800011 を加えると 0x800010 になります。他のオフセットを反復して、同じ演算が機能することを確認できます。

最後のステップ、free() 、簡単です:いつでも free() に戻るだけです。 malloc() のいずれかの値 、 calloc() または realloc() あなたに戻ってきました—それ以外は災害です。あなたは正しく mem を提供しました その価値を維持するために — ありがとう。無料でリリースします。

最後に、システムの malloc の内部について知っている場合は、 パッケージの場合、16 バイトでアラインされたデータ (または 8 バイトでアラインされている) を返す可能性が高いと推測できます。 16 バイトでアラインされていれば、値をいじる必要はありません。ただし、これは危険で移植性がありません — その他 malloc パッケージにはさまざまな最小アライメントがあるため、何か違うことをするときにあることを想定すると、コアダンプが発生します。広い範囲内で、このソリューションは移植可能です。

他の誰かが posix_memalign() について言及しました アラインされたメモリを取得する別の方法として。これはどこでも利用できるわけではありませんが、多くの場合、これをベースとして実装できます。アラインメントが 2 の累乗であると便利であることに注意してください。他の配置はより厄介です。

もう 1 つコメント — このコードは、割り当てが成功したかどうかをチェックしません。

修正

Windows Programmer は、ポインターに対してビット マスク操作を行うことはできないと指摘しました。実際、GCC (3.4.6 および 4.3.1 テスト済み) はそのように文句を言います。したがって、基本コードの修正バージョン (メイン プログラムに変換) は次のとおりです。また、指摘されているように、16 の代わりに 15 だけを自由に追加しました。 uintptr_t を使用しています C99 は、ほとんどのプラットフォームでアクセスできるほど長い間存在しているためです。 PRIXPTR の使用がなければ printf()#include <stdint.h> で十分です。 #include <inttypes.h> を使用する代わりに . [このコードには、C.R. が指摘した修正が含まれています。これは、何年も前に Bill K によって最初に指摘された点を繰り返していましたが、今まで見落としていました。]

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

static void memset_16aligned(void *space, char byte, size_t nbytes)
{
    assert((nbytes & 0x0F) == 0);
    assert(((uintptr_t)space & 0x0F) == 0);
    memset(space, byte, nbytes);  // Not a custom implementation of memset()
}

int main(void)
{
    void *mem = malloc(1024+15);
    void *ptr = (void *)(((uintptr_t)mem+15) & ~ (uintptr_t)0x0F);
    printf("0x%08" PRIXPTR ", 0x%08" PRIXPTR "\n", (uintptr_t)mem, (uintptr_t)ptr);
    memset_16aligned(ptr, 0, 1024);
    free(mem);
    return(0);
}

そして、これはわずかに一般化されたバージョンで、2 の累乗のサイズで機能します:

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

static void memset_16aligned(void *space, char byte, size_t nbytes)
{
    assert((nbytes & 0x0F) == 0);
    assert(((uintptr_t)space & 0x0F) == 0);
    memset(space, byte, nbytes);  // Not a custom implementation of memset()
}

static void test_mask(size_t align)
{
    uintptr_t mask = ~(uintptr_t)(align - 1);
    void *mem = malloc(1024+align-1);
    void *ptr = (void *)(((uintptr_t)mem+align-1) & mask);
    assert((align & (align - 1)) == 0);
    printf("0x%08" PRIXPTR ", 0x%08" PRIXPTR "\n", (uintptr_t)mem, (uintptr_t)ptr);
    memset_16aligned(ptr, 0, 1024);
    free(mem);
}

int main(void)
{
    test_mask(16);
    test_mask(32);
    test_mask(64);
    test_mask(128);
    return(0);
}

test_mask() を変換するには 汎用の割り当て関数に変換するには、アロケーターからの単一の戻り値でリリース アドレスをエンコードする必要があります。これは、複数の人が回答で示しているとおりです。

面接担当者の問題

Uri のコメント:今朝の読解力に問題があるのか​​もしれませんが、インタビューの質問で「1024 バイトのメモリをどのように割り当てますか」と具体的に述べられていて、明らかにそれ以上のメモリを割り当てているとします。それはインタビュアーからの自動的な失敗ではないでしょうか?

私の返信は 300 文字のコメントに収まりません...

場合によると思います。ほとんどの人 (私を含む) は、「1024 バイトのデータを格納できるスペースをどのように割り当て、ベース アドレスが 16 バイトの倍数であるか」という意味で質問を受け取ったと思います。インタビュアーが 1024 バイト (のみ) を割り当てて 16 バイトに揃える方法を本当に意味している場合、オプションはさらに制限されます。

  • 明らかに、1 つの可能性は、1024 バイトを割り当ててから、そのアドレスに「アライメント処理」を与えることです。このアプローチの問題点は、実際に使用可能なスペースが適切に決定されないことです (使用可能なスペースは 1008 から 1024 バイトの間ですが、どのサイズかを指定するメカニズムがありませんでした)。>
  • もう 1 つの可能性は、完全なメモリ アロケータを記述し、返される 1024 バイト ブロックが適切に配置されていることを確認することです。その場合、おそらく提案されたソリューションとほぼ同じ操作を行うことになりますが、アロケーター内に隠します。

ただし、インタビュアーがこれらの回答のいずれかを期待していた場合、この解決策が密接に関連する質問への回答であることを認識し、会話を正しい方向に向けるために質問を再構成することを期待します。 (さらに、面接担当者が本当にしつこい場合は、私はその仕事をしたくありません。不十分な正確さの要件に対する答えが訂正されずに炎上する場合、面接担当者は安全に仕事をすることができる人ではありません。)

世界は進む

質問のタイトルが最近変更されました。私を困惑させたのは、Solve the memoryaligning in C インタビューの質問でした .改訂されたタイトル (標準ライブラリのみを使用してアライメントされたメモリを割り当てる方法 ) はわずかに修正された回答を要求します — この補遺はそれを提供します.

C11 (ISO/IEC 9899:2011) 追加機能 aligned_alloc() :

そして POSIX は posix_memalign() を定義します :

現在、これらのいずれかまたは両方を使用して質問に回答できますが、質問が最初に回答されたときは POSIX 関数のみがオプションでした。

舞台裏では、新しい整列メモリ関数は、質問で概説されているのとほぼ同じ仕事をしますが、整列をより簡単に強制し、整列メモリの開始を内部的に追跡して、コードが特別に対処する必要があります — 使用された割り当て関数によって返されたメモリを解放するだけです。


質問の見方によって、わずかに異なる 3 つの回答:

1) 尋ねられた正確な質問には、Jonathan Leffler の解決策で十分です。ただし、16 アラインに切り上げるには、16 バイトではなく 15 バイトしか必要ありません。

あ:

/* allocate a buffer with room to add 0-15 bytes to ensure 16-alignment */
void *mem = malloc(1024+15);
ASSERT(mem); // some kind of error-handling code
/* round up to multiple of 16: add 15 and then round down by masking */
void *ptr = ((char*)mem+15) & ~ (size_t)0x0F;

B:

free(mem);

2) より一般的なメモリ割り当て関数の場合、呼び出し元は 2 つのポインター (使用するポインターと解放するポインター) を追跡する必要はありません。したがって、アラインされたバッファーの下にある「実際の」バッファーへのポインターを格納します。

あ:

void *mem = malloc(1024+15+sizeof(void*));
if (!mem) return mem;
void *ptr = ((char*)mem+sizeof(void*)+15) & ~ (size_t)0x0F;
((void**)ptr)[-1] = mem;
return ptr;

B:

if (ptr) free(((void**)ptr)[-1]);

(1) とは異なり、mem に追加されるのは 15 バイトだけですが、このコードは実際に 削減 できることに注意してください。 実装が malloc からの 32 バイト アラインメントを保証する場合のアラインメント (可能性は低いですが、理論的には C 実装は 32 バイト アラインされた型を持つことができます)。 memset_16aligned を呼び出すだけであれば問題ありませんが、構造体にメモリを使用する場合は問題になる可能性があります。

実装固有のアライメント保証が何であるかをプログラムで判断する方法がないため、これに対する適切な修正が何であるかはわかりません(返されたバッファが任意の構造体に必ずしも適しているとは限らないことをユーザーに警告することを除いて)。起動時に 2 つ以上の 1 バイト バッファーを割り当てることができると思います。表示される最悪のアラインメントが保証されたアラインメントであると想定します。間違っていると、メモリが無駄になります。より良いアイデアをお持ちの方は、そう言ってください...

[追加 :「標準的な」トリックは、必要なアラインメントを決定するために「最大限にアラインメントされる可能性が高い型」の結合を作成することです。最大限にアラインされた型は (C99 では) 'long long である可能性があります。 ', 'long double ', 'void * '、または 'void (*)(void) '; <stdint.h> を含める場合 、おそらく 'intmax_t を使用できます ' long long の代わりに (そして、Power 6 (AIX) マシンでは intmax_t 128 ビットの整数型が得られます)。そのユニオンのアラインメント要件は、単一の char の後にユニオンが続く構造体に埋め込むことによって決定できます。

struct alignment
{
    char     c;
    union
    {
        intmax_t      imax;
        long double   ldbl;
        void         *vptr;
        void        (*fptr)(void);
    }        u;
} align_data;
size_t align = (char *)&align_data.u.imax - &align_data.c;

次に、要求された配置 (例では 16) と align の大きい方を使用します。 上で計算された値。

(64 ビット) Solaris 10 では、malloc() からの結果の基本的なアライメントは は 32 バイトの倍数です。
]

実際には、アラインされたアロケーターは、ハードワイヤードではなく、アラインメントのパラメーターを取ることがよくあります。そのため、ユーザーは関心のある構造体のサイズ (またはそれ以上の最小の 2 のべき乗) を渡せば、すべて問題ありません。

3) プラットフォームが提供するものを使用します:posix_memalign POSIX の場合、_aligned_malloc

4) C11 を使用する場合、最もクリーンで移植性が高く簡潔なオプションは、標準ライブラリ関数 aligned_alloc を使用することです。 このバージョンの言語仕様で導入されました。


posix_memalign() を試すこともできます (もちろん、POSIX プラットフォーム上で)。