6

本の問題13.9、「コーディングインタビューのクラッキング」について質問があります。問題は、メモリの割り当てをサポートする整列された割り当ておよび解放関数を作成することです。その答えのコードは次のとおりです。

void *aligned_malloc(size_t required_bytes, size_t alignment) {
  void *p1;
  void **p2;
  int offset=alignment-1+sizeof（void*);
  if((p1=(void*)malloc(required_bytes+offset))==NULL)
  return NULL;
  p2=(void**)(((size_t)(p1)+offset)&~(alignment-1));  //line 5
  p2[-1]=p1; //line 6
  return p2;
}

私は5行目と6行目と非常に混同しています。すでにp1にオフセットを追加しているのに、なぜ「and」を実行する必要があるのですか？[-1]はどういう意味ですか？よろしくお願いします。

4

3 に答える 3

13

サンプル コードは完全ではありません。何も割り当てません。p1 ポインターを設定する malloc ステートメントが欠落していることは明らかです。私は本を​​持っていませんが、完全なコードは次の行に沿っているはずです。

void *aligned_malloc(size_t required_bytes, size_t alignment) {
    void *p1;
    void **p2;
    int offset=alignment-1+sizeof（void*);
    p1 = malloc(required_bytes + offset);               // the line you are missing
    p2=(void**)(((size_t)(p1)+offset)&~(alignment-1));  //line 5
    p2[-1]=p1; //line 6
    return p2;
}

それで...コードは何をしますか？

  • 戦略は、必要以上のスペースを (p1 に) malloc し、バッファーの先頭の後のどこかに p2 ポインターを返すことです。
  • アラインメントは 2 の累乗であるため、バイナリでは 1 の後にゼロが続く形式にする必要があります。たとえば、アライメントが 32 の場合、2 進数で 00100000 になります。
  • バイナリ形式の (alignment-1) は、1 を 0 に変換し、1 の後のすべての 0 を 1 に変換します。たとえば、(32-1) は 00011111 です。
  • ~ はすべてのビットを逆にします。つまり: 11100000
  • ここで、p1 はバッファーへのポインターです (バッファーは、必要なオフセット分だけ大きいことに注意してください)。p1 にオフセットを追加します: p1+offset。
  • したがって、(p1+offset) は、返したい値よりも大きくなります。ビット単位の and を実行して、重要でないビットをすべて nil します: (p1+offset) & ~(offset-1)
  • これは、返したいポインタ p2 です。最後の 5 桁が 0 であるため、要求どおりに 32 にアラインされていることに注意してください。
  • p2 が返されます。ただし、ユーザーがaligned_freeを呼び出したときにp1に到達できる必要があります。このために、オフセットを計算したときに、1 つの追加ポインターの場所を予約したことに注意してください (4 行目の sizeof(void*) です)。
  • したがって、p1 を p2 の直前に配置します。これは p2[-1] です。ちょっとややこしい計算です。p2 は void* として定義されていることに注意してください。それを見る1つの方法は、 void の配列としてです。C 配列の計算では、p2[0] は正確に p2 であると言われています。p2[1] は p2 + sizeof(void*) です。一般に、p2[n] = p2 + n*sizeof(void*) です。コンパイラは負の数もサポートするため、p2[-1] は p2 の前の 1 つの void* (通常は 4 バイト) です。

私は、aligned_free が次のようなものであると推測します:

void aligned_free( void* p ) {
    void* p1 = ((void**)p)[-1];         // get the pointer to the buffer we allocated
    free( p1 );
}
于 2012-09-20T01:28:16.217 に答える
11

p1は実際の割り当てです。p2は返されるポインタであり、割り当てポイントを超えてメモリを参照し、最初に実際に割り当てられたポインタを整列および格納するための十分なスペースを残します。align_free（）が呼び出されると、「実際の」free（）を実行するためにp1が取得されます。

ビット数学に関しては、それはもう少し面倒になりますが、それは機能します。

p2=(void**)(((size_t)(p1)+offset)&~(alignment-1));  //line 5

p1が実際の割り当て参照であることを忘れないでください。キックの場合、32ビットポインタを使用して次のことを想定します。

alignment = 64 bytes, 0x40
offset = 0x40-1+4 = 0x43
p1 = 0x20000110, a value returned from the stock malloc()

重要なのは、malloc()元の要求の上に、さらに0x43バイトのスペースを割り当てる元の要求です。これは、アライメント計算と32ビットポインタのスペースの両方を確実に考慮できるようにするためです。

p2=(void**)(((size_t)(p1)+offset)&~(alignment-1));  //line 5
p2 = (0x20000110 + 0x43) &~ (0x0000003F)
p2 = 0x20000153 &~ 0x0000003F
p2 = 0x20000153 & 0xFFFFFFC0
p2 = 0x20000140

p2は0x40境界に配置され（つまり、0x3Fのすべてのビットは0）、p1によって参照される元の割り当て用の4バイトポインターを格納するのに十分なスペースが残されます。

アラインメントの計算をしてからずっと経ちましたので、ビットが足りなくなったら、誰かがこれを修正してください。

于 2012-09-20T00:54:44.010 に答える