14

そのため、C99 は、一般的に使用される「柔軟な配列メンバー」ハックをstruct祝福して、サイズ要件に合わせて過剰に割り当てられる s を作成できるようにしました。これを行うことはほとんどの正常な実装で完全に安全だと思いますが、特定の状況で a の一部のメンバーが必要ないことがわかっている場合、C で「過小割り当て」することは合法structですか?

抽象的な例

タイプがあるとします：

struct a {
  bool   data_is_x;
  void * data;
  size_t pos;
};

の場合data_is_x、 の型はメンバーdataを使用する必要がある型です。posそれ以外の場合、これを操作する関数は、のこの特定のコピーのメンバーをstruct必要としません。本質的に、 はメンバーを持っているかどうかに関する情報を保持し、この情報はの有効期間内に変更されません (悪意のあるいたずら以外では、とにかくほとんどすべてが壊れます)。言うのは安全ですか：posstructstructposstruct

struct a *a = malloc(data_is_x ? sizeof(struct a) : offsetof(struct a, pos));

posメンバーが必要な場合にのみメンバーにスペースを割り当てるのはどれですか? structそれとも、問題のメンバーを使用したことがない場合でも、ポインタに対して小さすぎるキャスト空間を使用するという制約に違反していますか?

具体例

私の実際のユースケースは少し複雑です。主にここにあるのは、なぜ私がこれをやりたいのかを理解できるようにするためです。

typedef struct {
  size_t size;
  void * data;
  size_t pos;
} mylist;

for のコードはmylist_create、 forが項目長 (項目が何であれ) である連続したデータの配列であるがsize > 0、 forは項目を含む双方向リンク リストの現在のノードであることを指定します。sで動作するすべての関数は、. 存在する場合、データをリンクされたリストとして処理し、「現在の」インデックスがノードを指すようにします。そうでない場合は、「現在の」インデックスが に格納された配列としてデータを処理します。datasizesize == 0mylistsize == 0datapos

メンバーがsize == 0本当に必要ない場合ですが、必要な場合は. だから私の質問は、これを行うことは合法ですか：possize > 0

mylist *list = malloc(size ? sizeof(mylist) : offsetof(mylist, pos));

(未定義の動作のペナルティで) ながら、メンバーにアクセスしようとしない (またはアクセスする必要がない) ことを保証する場合は? それとも、これを行うことを考えるのはUBであると標準のどこかに書かれていますか?size == 0pos

4

5 に答える 5

4

malloc itself doesn't care at all how much memory you allocate for a structure, it's the dereferencing of memory outside the block that is undefined. From C99 6.5.3.2 Address and indirection operators:

If an invalid value has been assigned to the pointer, the behavior of the unary * operator is undefined.

And, from 7.20.3 Memory management functions, we find (my italics):

The pointer returned if the allocation succeeds is suitably aligned so that it may be assigned to a pointer to any type of object and then used to access such an object or an array of such objects in the space allocated (until the space is explicitly deallocated).

Hence, you can do something like:

typedef struct { char ch[100]; } ch100;
ch100 *c = malloc (1);

and, provided you only ever try to do anything with c->ch[0], it's perfectly acceptable.

For your specific concrete example, I'm not too sure I'd be that worried, assuming that what you're concerned about is storage space. If you're concerned for other reasons, feel free to ignore this bit, especially since the assumptions included within are not mandated by the standard.

From my understanding, you have a structure:

typedef struct {
  size_t size;
  void * data;
  size_t pos;
} mylist;

where you want to use only data where size is 0, and both data and pos where size is greater than 0. This precludes the use of putting data and pos in a union.

A significant number of malloc implementations will round up your requested space to a multiple of 16 bytes (or some greater power of two) in order to ease memory fragmentation issues. This isn't required by the standard of course, but it is pretty common.

Assuming (for example) 32-bit pointers and size_t, your twelve bytes of structure will most likely take up a 16-byte arena header and a 16-byte chunk for the data. This chunk would still be 16 bytes even if you only asked for 8 (ie. without pos).

If you had 64-bit pointer and size_t types, it might make a difference - 24 bytes with pos and 16 without.

But even then, unless you're allocating a lot of these structures, it may not be a problem.

于 2011-09-09T02:12:46.887 に答える
2

これは完全に合法ですが、おそらく 2 つの構造体を使用することでわかりにくくする必要があります。

struct leaf_node {
    size_t size;
    void *data;
    size_t pos;
};
struct linked_node {
    size_t size;
    void *next;
};

void *in = ...;

if (*(size_t*)(in) == 0) {
    struct leaf_node *node = in;
    ...
} else {
    struct linked_node *node = in;
    ....
}

これは、paxdiablo が引用した、ポインターを任意のデータ ポインターにキャストできるという標準と密接に関連しています。このようにすると、割り当てられたバッファーに収まる構造体にキャストすることも常に確認されます (不要ですが便利な機能です)。

32 ビット システムでの 16 バイトの最小サイズについて paxdiablo が言ったことは多くの場合真実ですが、それを回避するために大きなチャンクを割り当てることができます。

32 ビット システムでは、linked_node は 8 バイトを使用します。やろうとしていることから利益を得るには、プールを使用する必要があります。

struct leaf_node *leaf_pool = malloc(N*sizeof(struct leaf_node));
struct linked_node *linked_pool = malloc(N*sizeof(struct linked_node));

もちろん、プールを再割り当てするべきではありませんが、必要に応じて新しいプールを割り当て、ノードを再利用してください。この場合、シングルleaf_nodeは 12 バイトを使用します。

にも同じことが当てはまりlinked_nodeます。プールに割り当てると、16 バイトではなく 8 バイトが使用されます。

構造体が GCC で使用されていない限り、パフォーマンスのボトルネックはありません__attribute__ ((packed))。その場合、構造体のアライメントが非常に悪くなる可能性があります。たとえば、構造体に 13 バイトのサイズを与える余分な char がある場合は特にそうです。

最初の質問に戻ると、割り当てられたデータを指すために使用するポインターは、バッファーの外部のデータにアクセスしないことを確認する限り問題ではありません。構造体は基本的に char 文字列に似ており、最初の size_t が「null バイト」であるかどうかを確認します。そうであれば、バッファーが小さいと想定します。null でない場合は、「文字列」が長いと見なされ、より多くのデータを読み取ることになります。まったく同じリスクが伴い、コンパイル後の唯一の違いは、読み取られる要素ごとのサイズです。[el]を使用して segfault を簡単に発生させることで確認できるため、構造体ポインターへのキャストや要素の読み取りと比較して、for 文字列の使用について魔法は何もありません[el]。

于 2011-09-09T08:10:03.160 に答える
1

私の知る限り、すべてのメンバーアクセスは集約へのアクセスでもあるため、有効な型を宣言します。つまり、その型の値を実際に含めるには小さすぎる割り当てられたオブジェクトを取得します。

これは未定義の動作のように聞こえますが、実際には標準からそれを元に戻すことはできません。また、他の解釈をサポートする合理的な議論もあります。

于 2011-09-09T15:13:07.623 に答える
1

4 バイトまたは 8 バイトを節約していると思うかもしれませんが、メモリ割り当ては調整できます。gcc を使用していて、その 16 バイトにアラインされている場合、次のような結果が得られます。

for (int i = 0; i <= 64; i++) {
    char *p = (char *) malloc(i);
    char *q = (char *) malloc(i);
    long long t = q - p;
    cout << "malloc(" << i << ") used " << t << " bytes " << endl;
}

版画

malloc(0) used 32 bytes 
malloc(1) used 32 bytes 
malloc(2) used 32 bytes 
malloc(3) used 32 bytes 
malloc(4) used 32 bytes 
malloc(5) used 32 bytes 
malloc(6) used 32 bytes 
malloc(7) used 32 bytes 
malloc(8) used 32 bytes 
malloc(9) used 32 bytes 
malloc(10) used 32 bytes 
malloc(11) used 32 bytes 
malloc(12) used 32 bytes 
malloc(13) used 32 bytes 
malloc(14) used 32 bytes 
malloc(15) used 32 bytes 
malloc(16) used 32 bytes 
malloc(17) used 32 bytes 
malloc(18) used 32 bytes 
malloc(19) used 32 bytes 
malloc(20) used 32 bytes 
malloc(21) used 32 bytes 
malloc(22) used 32 bytes 
malloc(23) used 32 bytes 
malloc(24) used 32 bytes 
malloc(25) used 48 bytes 
malloc(26) used 48 bytes 
malloc(27) used 48 bytes 
malloc(28) used 48 bytes 
malloc(29) used 48 bytes 
malloc(30) used 48 bytes 
malloc(31) used 48 bytes 
malloc(32) used 48 bytes 
malloc(33) used 48 bytes 
malloc(34) used 48 bytes 
malloc(35) used 48 bytes 
malloc(36) used 48 bytes 
malloc(37) used 48 bytes 
malloc(38) used 48 bytes 
malloc(39) used 48 bytes 
malloc(40) used 48 bytes 
malloc(41) used 64 bytes 
malloc(42) used 64 bytes 
malloc(43) used 64 bytes 
malloc(44) used 64 bytes 
malloc(45) used 64 bytes 
malloc(46) used 64 bytes 
malloc(47) used 64 bytes 
malloc(48) used 64 bytes 
malloc(49) used 64 bytes 
malloc(50) used 64 bytes 
malloc(51) used 64 bytes 
malloc(52) used 64 bytes 
malloc(53) used 64 bytes 
malloc(54) used 64 bytes 
malloc(55) used 64 bytes 
malloc(56) used 64 bytes 
malloc(57) used 80 bytes 
malloc(58) used 80 bytes 
malloc(59) used 80 bytes 
malloc(60) used 80 bytes 
malloc(61) used 80 bytes 
malloc(62) used 80 bytes 
malloc(63) used 80 bytes 
malloc(64) used 80 bytes

システムによっては、malloc(0) と malloc(24) のどちらを使用しても同じ量のメモリが使用される場合があります。

于 2011-09-09T20:59:27.010 に答える
0

割り当てで 4 バイトを節約することは、何万ものものについて話している場合を除き、ほとんど意味がありません。それらを常に解放して再割り当てするのではなく、リスト (「プール」) にします。速くなることは保証します。しかし、このようなスキームをきれいに使用するには、再利用可能なすべてのパーツが簡単に交換可能である必要があります。つまり、"size_t pos" メンバーが必要です。

ですから、そうです、あなたがやろうとしていることは完全に合法です。複雑さとそれが課す柔軟性の欠如に見合うだけの価値があるかどうかはわかりません.

于 2011-09-09T16:06:01.050 に答える