なぜdlmallocに割り当てられたチャンクヘッダーに4バイト前の割り当て済みチャンクが含まれています

Question

ヒープ上にメモリを割り当てるのに最適な方法を使用するdoug leaメモリアロケータと呼ばれるダイナミックメモリアロケータを使いました。アルゴリズムは他の多くのアルゴリズムの基礎ですが、割り当てられたチャンクの場合、そのチャンクのヘッダーには前のチャンクの最後の4バイトのデータが含まれています。私はアルゴリズムの説明をチェックしましたが、理由を見つけることができませんでした。以前のチャンクの4バイトの割り当ての目的は何ですか？ 私はまた、スペースの同期と適切な使用のための他の塊の.dtorsセクションの割り当てとして、詳細を知りたいと思っています。

this is the figure of chunks of dlmalloc algorithm

上の図は、割り当てられたチャンクと空きチャンクの構造が含まれています。空きチャンクでは、最初の4バイトには前のチャンクのサイズが含まれますが、割り当てられたチャンクには最初の4バイトにはが含まれています。先ほど割り当てたチャンクのユーザデータの最後の4バイトは少し混乱しています。現在のチャンク内の以前に割り当てられたチャンクの4バイトだけを割り当てる目的は何か。

Answer 1

私は、具体的dlmallocを学んだが、ここでは可能性のある説明であるしていない：16バイトアライメントを必要とするオブジェクトを持つアーキテクチャでは

場合（インテルSSEが行うように）、返されたアドレスは16の倍数でなければなりませんヘッダは、チャンクのサイズを含む12バイトの情報と、チャンクを前のものと合体させるためのいくつかのリンケージ情報とを有し、ヘッダは長さが16であると定義され、最初の4バイトは前に割り当てられたチャンク。この前のチャンクが空いている場合、このスペースは最適化のためにアロケータによって使用される可能性があります。

Answer 2

はいチャンクは重複します。かつて、メモリは非常に高価でした。 これは、dlmalloc、ptmalloc、およびglibc mallocの機能です。

This struct declaration is misleading (but accurate and necessary). 
It declares a "view" into memory allowing access to necessary 
fields at known offsets from a given base. See explanation below. 

struct malloc_chunk { 

INTERNAL_SIZE_T  prev_size; /* Size of previous chunk (if free). */ 
INTERNAL_SIZE_T  size;  /* Size in bytes, including overhead. */ 

struct malloc_chunk* fd;   /* double links -- used only if free. */ 
struct malloc_chunk* bk; 
}; 

malloc_chunk詳細：

(The following includes lightly edited explanations by Colin Plumb.) 

Chunks of memory are maintained using a `boundary tag' method as 
described in e.g., Knuth or Standish. (See the paper by Paul 
Wilson ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a 
survey of such techniques.) Sizes of free chunks are stored both 
in the front of each chunk and at the end. This makes 
consolidating fragmented chunks into bigger chunks very fast. The 
size fields also hold bits representing whether chunks are free or 
in use. 

An allocated chunk looks like this: 


chunk->+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 
     |    Size of previous chunk, if allocated   | | 
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 
     |    Size of chunk, in bytes       |P| 
    mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 
     |    User data starts here...       . 
     .                . 
     .    (malloc_usable_space() bytes)      . 
     .                | 
next ->+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 
     |    Size of chunk          | 
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 


Where "chunk" is the front of the chunk for the purpose of most of 
the malloc code, but "mem" is the pointer that is returned to the 
user. "Nextchunk" is the beginning of the next contiguous chunk. 

Chunks always begin on even word boundries, so the mem portion 
(which is returned to the user) is also on an even word boundary, and 
thus at least double-word aligned. 

Free chunks are stored in circular doubly-linked lists, and look like this: 

chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 
     |    Size of previous chunk       | 
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 
`head:' |    Size of chunk, in bytes       |P| 
    mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 
     |    Forward pointer to next chunk in list    | 
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 
     |    Back pointer to previous chunk in list   | 
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 
     |    Unused space (may be 0 bytes long)    . 
     .                . 
     .                | 
next-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 
`foot:' |    Size of chunk, in bytes       | 
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 

The P (PREV_INUSE) bit, stored in the unused low-order bit of the 
chunk size (which is always a multiple of two words), is an in-use 
bit for the *previous* chunk. If that bit is *clear*, then the 
word before the current chunk size contains the previous chunk 
size, and can be used to find the front of the previous chunk. 
The very first chunk allocated always has this bit set, 
preventing access to non-existent (or non-owned) memory. If 
prev_inuse is set for any given chunk, then you CANNOT determine 
the size of the previous chunk, and might even get a memory 
addressing fault when trying to do so. 

Note that the `foot' of the current chunk is actually represented 
as the prev_size of the NEXT chunk. This makes it easier to 
deal with alignments etc but can be very confusing when trying 
to extend or adapt this code. 

The two exceptions to all this are 

1. The special chunk `top' doesn't bother using the 
    trailing size field since there is no next contiguous chunk 
    that would have to index off it. After initialization, `top' 
    is forced to always exist. If it would become less than 
    MINSIZE bytes long, it is replenished. 

2. Chunks allocated via mmap, which have the second-lowest-order 
    bit (IS_MMAPPED) set in their size fields. Because they are 
    allocated one-by-one, each must contain its own trailing size field.