元の答え
{
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」の意味は主に、基本型 ( 、、、オブジェクトへのポインター、および関数へのポインター) のようなものを意味します。グラフィックス システムで遊ぶなど、より専門的なことを行う場合、システムの残りの部分よりも厳密な調整が必要になる可能性があります。そのため、このような質問と回答があります。)long
double
long double
long long
次のステップは、void ポインターを char ポインターに変換することです。GCC にもかかわらず、void ポインターでポインター演算を行うことは想定されていません (また、GCC には、それを悪用した場合に通知する警告オプションがあります)。次に、開始ポインターに 16 を追加します。0x800001malloc()
というありえないほどアラインされていないポインタが返されたとします。16 を追加すると、0x800011 が得られます。ここで、16 バイト境界に切り捨てたいので、最後の 4 ビットを 0 にリセットします。0x0F は最後の 4 ビットを 1 に設定します。したがって、~0x0F
最後の 4 つを除くすべてのビットが 1 に設定されます。それに 0x800011 を加えると 0x800010 になります。他のオフセットを反復して、同じ演算が機能することを確認できます。
最後のステップ ,free()
は簡単です. , の 1 つまたは自分に返された値に常に戻るだけです.free()
それ以外は災害です. あなたはその値を保持するために正しく提供しました — ありがとう。フリーはそれをリリースします。malloc()
calloc()
realloc()
mem
最後に、システムのパッケージの内部構造を知っていれば、malloc
16 バイト アラインされたデータ (または 8 バイト アライン) を返す可能性が高いと推測できます。16 バイトでアラインされていれば、値をいじる必要はありません。ただし、これは危険で移植性がありません。他のmalloc
パッケージには最小アライメントが異なるため、別のことを行うときに 1 つのことを想定すると、コア ダンプが発生します。広い範囲内で、このソリューションは移植可能です。
posix_memalign()
アラインされたメモリを取得する別の方法として、他の誰かが言及しました。これはどこでも利用できるわけではありませんが、多くの場合、これをベースとして実装できます。アラインメントが 2 の累乗であると便利であることに注意してください。他のアライメントはより厄介です。
もう 1 つコメントします。このコードは、割り当てが成功したかどうかをチェックしません。
修正
Windows Programmerは、ポインターに対してビット マスク操作を行うことはできないと指摘しました。実際、GCC (3.4.6 および 4.3.1 テスト済み) はそのように文句を言います。したがって、基本コードの修正バージョン (メイン プログラムに変換) は次のとおりです。また、指摘されているように、16 の代わりに 15 だけを自由に追加しました。私が使用しuintptr_t
ているのは、C99 がほとんどのプラットフォームでアクセスできるようになってからです。PRIXPTR
ステートメントで を使用しない場合は、代わりに を使用printf()
するだけで十分です。[このコードにはCRによって指摘された修正が含まれています。これは、何年も前にBill Kによって最初に指摘された点を繰り返したものであり、私は今まで見落としていました。]#include <stdint.h>
#include <inttypes.h>
#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 バイト ブロックが適切に配置されていることを確認することです。その場合、提案されたソリューションとかなり似た操作を実行することになる可能性がありますが、アロケーター内に隠します。
ただし、面接担当者がこれらの回答のいずれかを期待していた場合、この解決策が密接に関連する質問への回答であることを認識し、会話を正しい方向に向けるために質問を再構成することを期待します。(さらに、もし面接官が本当にしつこいなら、私はその仕事をしたくありません; 不十分な正確さの要件への答えが訂正されずに炎上するなら、その面接官は安全に働くことができる人ではありません. )
世界は進む
質問のタイトルが最近変更されました。私を困惑させたのは、C のインタビューの質問でメモリ アラインメントを解決することでした。改訂されたタイトル (標準ライブラリのみを使用してアラインされたメモリを割り当てる方法は? ) は、わずかに改訂された回答を要求しています — この補遺はそれを提供します。
C11 (ISO/IEC 9899:2011) 追加機能aligned_alloc()
:
7.22.3.1aligned_alloc
関数
あらすじ
#include <stdlib.h>
void *aligned_alloc(size_t alignment, size_t size);
説明
この関数は、アラインメントが で指定され、サイズが で指定され、値が不定でaligned_alloc
あるオブジェクトにスペースを割り当てます。の値は、実装によってサポートされている有効なアライメントであり、 の値はの整数倍でなければなりません。alignment
size
alignment
size
alignment
戻り値
このaligned_alloc
関数は、NULL ポインターまたは割り当てられたスペースへのポインターを返します。
また、POSIX では次のように定義されていますposix_memalign()
。
#include <stdlib.h>
int posix_memalign(void **memptr, size_t alignment, size_t size);
説明
このposix_memalign()
関数は、 でsize
指定された境界に整列されたバイトを割り当てalignment
、 で割り当てられたメモリへのポインタを返しますmemptr
。の値はalignment
の 2 乗の倍数である必要がありsizeof(void *)
ます。
正常に完了すると、 が指す値はmemptr
の倍数になりalignment
ます。
要求されたスペースのサイズが 0 の場合、動作は実装定義です。で返される値はmemptr
、ヌル ポインターまたは一意のポインターのいずれかになります。
このfree()
関数は、以前に によって割り当てられたメモリの割り当てを解除しますposix_memalign()
。
戻り値
正常に完了すると、posix_memalign()
ゼロを返します。それ以外の場合は、エラーを示すためにエラー番号が返されます。
現在、これらのいずれかまたは両方を使用して質問に回答できますが、質問が最初に回答されたときは、POSIX 関数のみがオプションでした。
舞台裏では、新しい整列メモリ関数は、質問で概説されているのとほぼ同じ仕事をしますが、整列をより簡単に強制し、整列メモリの開始を内部的に追跡して、コードが特別に対処する必要があります—使用された割り当て関数によって返されたメモリを解放するだけです。