mirror of
https://github.com/boostorg/pool.git
synced 2026-01-23 05:42:27 +00:00
d88008b987
that use it are valid. Merged revisions 53047-53048 via svnmerge from https://svn.boost.org/svn/boost/trunk ........ r53047 | danieljames | 2009-05-16 15:17:20 +0100 (Sat, 16 May 2009) | 1 line Fix some validation errors. ........ r53048 | danieljames | 2009-05-16 15:23:59 +0100 (Sat, 16 May 2009) | 1 line Use a local copy of the valid HTML 4.01 icon. ........ [SVN r53258]
872 lines
28 KiB
HTML
872 lines
28 KiB
HTML
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
|
|
"http://www.w3.org/TR/html4/loose.dtd">
|
|
|
|
<html>
|
|
<head>
|
|
<meta http-equiv="Content-Language" content="en-us">
|
|
<meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
|
|
<link href="../pool.css" rel="stylesheet" type="text/css">
|
|
|
|
<title>Guaranteeing Alignment</title>
|
|
</head>
|
|
|
|
<body>
|
|
<img src="../../../../boost.png" width="276" height="86" alt="C++ Boost">
|
|
|
|
<h1 align="center">Guaranteeing Alignment</h1>
|
|
|
|
<h2>Terminology</h2>
|
|
|
|
<p>Review the <a href="../concepts.html">concepts document</a> if you are
|
|
not already familiar with it. Remember that <em>block</em> is a contiguous
|
|
section of memory, which is <em>partitioned</em> or <em>segregated</em>
|
|
into fixed-size <em>chunks</em>. These <em>chunks</em> are what are
|
|
allocated and deallocated by the user.</p>
|
|
|
|
<h2>Overview</h2>
|
|
|
|
<p>Each <span class="code">Pool</span> has a single free list that can
|
|
extend over a number of memory blocks. Thus, <span class="code">Pool</span>
|
|
also has a linked list of allocated memory blocks. Each memory block, by
|
|
default, is allocated using <span class="code">new[]</span>, and all memory
|
|
blocks are freed on destruction. It is the use of <span class=
|
|
"code">new[]</span> that allows us to guarantee alignment.</p>
|
|
|
|
<h2>Proof of Concept: Guaranteeing Alignment</h2>
|
|
|
|
<p>Each block of memory is allocated as a POD type (specifically, an array
|
|
of characters) through <span class="code">operator new[]</span>. Let
|
|
<em>POD_size</em> be the number of characters allocated.</p>
|
|
|
|
<h3>Predicate 1: Arrays may not have padding</h3>
|
|
|
|
<p>This follows from the following quote:</p>
|
|
|
|
<p>[5.3.3/2] (Expressions::Unary expressions::Sizeof) "... When applied to
|
|
an array, the result is the total number of bytes in the array. This implies
|
|
that the size of an array of <em>n</em> elements is <em>n</em>
|
|
times the size of an element."</p>
|
|
|
|
<p>Therefore, arrays cannot contain padding, though the elements within the
|
|
arrays may contain padding.</p>
|
|
|
|
<h3>Predicate 2: Any block of memory allocated as an array of characters
|
|
through <span class="code">operator new[]</span> (hereafter referred to as
|
|
<em>the block</em>) is properly aligned for any object of that size or
|
|
smaller</h3>
|
|
|
|
<p>This follows from:</p>
|
|
|
|
<ul>
|
|
<li>[3.7.3.1/2] (Basic concepts::Storage duration::Dynamic storage
|
|
duration::Allocation functions) "... The pointer returned shall be
|
|
suitably aligned so that it can be converted to a pointer of any complete
|
|
object type and then used to access the object or array in the storage
|
|
allocated ..."</li>
|
|
|
|
<li>[5.3.4/10] (Expressions::Unary expressions::New) "... For arrays of
|
|
<span class="code">char</span> and <span class="code">unsigned char</span>,
|
|
the difference between the result of the
|
|
<em>new-expression</em> and the address returned by the allocation
|
|
function shall be an integral multiple of the most stringent alignment
|
|
requirement (3.9) of any object type whose size is no greater than the
|
|
size of the array being created. [<em>Note:</em> Because allocation
|
|
functions are assumed to return pointers to storage that is appropriately
|
|
aligned for objects of any type, this constraint on array allocation
|
|
overhead permits the common idiom of allocating character arrays into
|
|
which objects of other types will later be placed. ]"</li>
|
|
</ul>
|
|
|
|
<h3>Consider: imaginary object type <em>Element</em> of a size which is a
|
|
multiple of some actual object size; assume sizeof(Element) > POD_size</h3>
|
|
|
|
<p>Note that an object of that size <em>can</em> exist. One object of that
|
|
size is an array of the "actual" objects.</p>
|
|
|
|
<p>Note that the block is properly aligned for an Element. This directly
|
|
follows from Predicate 2.</p>
|
|
|
|
<h3>Corollary 1: The block is properly aligned for an array of Elements</h3>
|
|
|
|
<p>This follows from Predicates 1 and 2, and the following quote:</p>
|
|
|
|
<p>[3.9/9] (Basic concepts::Types) "An <em>object type</em> is a (possibly
|
|
cv-qualified) type that is not a function type, not a reference type, and
|
|
not a void type." (Specifically, array types are object types.)</p>
|
|
|
|
<h3>Corollary 2: For any pointer <em>p</em> and integer <em>i</em>, if p is
|
|
properly aligned for the type it points to, then p + i (when well-defined)
|
|
is properly aligned for that type; in other words, if an array is properly
|
|
aligned, then each element in that array is properly aligned</h3>
|
|
|
|
<p>There are no quotes from the Standard to directly support this argument,
|
|
but it fits the common conception of the meaning of "alignment".</p>
|
|
|
|
<p>Note that the conditions for p + i being well-defined are outlined in
|
|
[5.7/5]. We do not quote that here, but only make note that it is
|
|
well-defined if p and p + i both point into or one past the same array.</p>
|
|
|
|
<h3>Let: sizeof(Element) be the least common multiple of sizes of several
|
|
actual objects (T<sub>1</sub>, T<sub>2</sub>, T<sub>3</sub>, ...)</h3>
|
|
|
|
<h3>Let: <em>block</em> be a pointer to the memory block, <em>pe</em> be
|
|
(Element *) block, and <em>p<sub>n</sub></em> be (T<sub>n</sub> *) block</h3>
|
|
|
|
<h3>Corollary 3: For each integer <em>i</em>, such that pe + i is
|
|
well-defined, then for each <em>n</em>, there exists some integer
|
|
<em>j<sub>n</sub></em> such that p<sub>n</sub> + j<sub>n</sub> is
|
|
well-defined and refers to the same memory address as pe + i</h3>
|
|
|
|
<p>This follows naturally, since the memory block is an array of Elements,
|
|
and for each n, sizeof(Element) % sizeof(T<sub>n</sub>) == 0; thus, the
|
|
boundary of each element in the array of Elements is also a boundary of each
|
|
element in each array of T<sub>n</sub>.</p>
|
|
|
|
<h3>Theorem: For each integer <em>i</em>, such that pe + i is well-defined,
|
|
that address (pe + i) is properly aligned for each type T<sub>n</sub></h3>
|
|
|
|
<p>Since pe + i is well-defined, then by Corollary 3, p<sub>n</sub> + j<sub>n</sub>
|
|
is well-defined. It is properly aligned from Predicate 2 and Corollaries 1
|
|
and 2.</p>
|
|
|
|
<h2>Use of the Theorem</h2>
|
|
|
|
<p>The proof above covers alignment requirements for cutting chunks out of a
|
|
block. The implementation uses actual object sizes of:</p>
|
|
|
|
<ul>
|
|
<li>The requested object size (requested_size); this is the size of chunks
|
|
requested by the user</li>
|
|
|
|
<li>void * (pointer to void); this is because we interleave our free list
|
|
through the chunks</li>
|
|
|
|
<li>size_type; this is because we store the size of the next block within
|
|
each memory block</li>
|
|
</ul>
|
|
|
|
<p>Each block also contains a pointer to the next block; but that is stored
|
|
as a pointer to void and cast when necessary, to simplify alignment
|
|
requirements to the three types above.</p>
|
|
|
|
<p>Therefore, <span class="code">alloc_size</span> is defined to be the lcm
|
|
of the sizes of the three types above.</p>
|
|
|
|
<h2>A Look at the Memory Block</h2>
|
|
|
|
<p>Each memory block consists of three main sections. The first section is
|
|
the part that chunks are cut out of, and contains the interleaved free list.
|
|
The second section is the pointer to the next block, and the third section
|
|
is the size of the next block.</p>
|
|
|
|
<p>Each of these sections may contain padding as necessary to guarantee
|
|
alignment for each of the next sections. The size of the first section is
|
|
number_of_chunks * lcm(requested_size, sizeof(void *), sizeof(size_type));
|
|
the size of the second section is lcm(sizeof(void *), sizeof(size_type); and
|
|
the size of the third section is sizeof(size_type).</p>
|
|
|
|
<p>Here's an example memory block, where requested_size == sizeof(void *) ==
|
|
sizeof(size_type) == 4:</p>
|
|
|
|
<table cellspacing="0" cellpadding="0" border="3" style="clear: both;"
|
|
align="center" summary="">
|
|
<caption>
|
|
<em>Memory block containing 4 chunks, showing overlying array
|
|
structures; FLP = Interleaved Free List Pointer</em>
|
|
</caption>
|
|
|
|
<tr>
|
|
<th>Sections</th>
|
|
|
|
<th>size_type alignment</th>
|
|
|
|
<th>void * alignment</th>
|
|
|
|
<th>requested_size alignment</th>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: red; text-align: center;" colspan="4">
|
|
Memory not belonging to process</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: gray; text-align: center;" rowspan="4">
|
|
Chunks section (16 bytes)</td>
|
|
|
|
<td style="background-color: gray; text-align: center;">(4 bytes)</td>
|
|
|
|
<td style="background-color: gray; text-align: center;">FLP for Chunk 1
|
|
(4 bytes)</td>
|
|
|
|
<td style="background-color: gray; text-align: center;">Chunk 1 (4
|
|
bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: silver; text-align: center;">(4 bytes)</td>
|
|
|
|
<td style="background-color: silver; text-align: center;">FLP for Chunk
|
|
2 (4 bytes)</td>
|
|
|
|
<td style="background-color: silver; text-align: center;">Chunk 2 (4
|
|
bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: gray; text-align: center;">(4 bytes)</td>
|
|
|
|
<td style="background-color: gray; text-align: center;">FLP for Chunk 3
|
|
(4 bytes)</td>
|
|
|
|
<td style="background-color: gray; text-align: center;">Chunk 3 (4
|
|
bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: silver; text-align: center;">(4 bytes)</td>
|
|
|
|
<td style="background-color: silver; text-align: center;">FLP for Chunk
|
|
4 (4 bytes)</td>
|
|
|
|
<td style="background-color: silver; text-align: center;">Chunk 4 (4
|
|
bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: silver; text-align: center;">Pointer to
|
|
next Block (4 bytes)</td>
|
|
|
|
<td style="background-color: gray; text-align: center;">(4 bytes)</td>
|
|
|
|
<td style="background-color: gray; text-align: center;">Pointer to next
|
|
Block (4 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: gray; text-align: center;">Size of next
|
|
Block (4 bytes)</td>
|
|
|
|
<td style="background-color: silver; text-align: center;">Size of next
|
|
Block (4 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: red; text-align: center;" colspan="4">
|
|
Memory not belonging to process</td>
|
|
</tr>
|
|
</table>
|
|
|
|
<p>To show a visual example of possible padding, here's an example memory
|
|
block where requested_size == 8 and sizeof(void *) == sizeof(size_type) ==
|
|
4:</p>
|
|
|
|
<table cellspacing="0" cellpadding="0" border="3" style="clear: both;"
|
|
align="center" summary="">
|
|
<caption>
|
|
<em>Memory block containing 4 chunks, showing overlying array
|
|
structures; FLP = Interleaved Free List Pointer</em>
|
|
</caption>
|
|
|
|
<tr>
|
|
<th>Sections</th>
|
|
|
|
<th>size_type alignment</th>
|
|
|
|
<th>void * alignment</th>
|
|
|
|
<th>requested_size alignment</th>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: red; text-align: center;" colspan="4">
|
|
Memory not belonging to process</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: gray; text-align: center;" rowspan="8">
|
|
Chunks section (32 bytes)</td>
|
|
|
|
<td style="background-color: gray; text-align: center;">(4 bytes)</td>
|
|
|
|
<td style="background-color: gray; text-align: center;">FLP for Chunk 1
|
|
(4 bytes)</td>
|
|
|
|
<td style="background-color: gray; text-align: center;" rowspan="2">
|
|
Chunk 1 (8 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: silver; text-align: center;">(4 bytes)</td>
|
|
|
|
<td style="background-color: silver; text-align: center;">(4 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: gray; text-align: center;">(4 bytes)</td>
|
|
|
|
<td style="background-color: gray; text-align: center;">FLP for Chunk 2
|
|
(4 bytes)</td>
|
|
|
|
<td style="background-color: silver; text-align: center;" rowspan="2">
|
|
Chunk 2 (8 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: silver; text-align: center;">(4 bytes)</td>
|
|
|
|
<td style="background-color: silver; text-align: center;">(4 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: gray; text-align: center;">(4 bytes)</td>
|
|
|
|
<td style="background-color: gray; text-align: center;">FLP for Chunk 3
|
|
(4 bytes)</td>
|
|
|
|
<td style="background-color: gray; text-align: center;" rowspan="2">
|
|
Chunk 3 (8 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: silver; text-align: center;">(4 bytes)</td>
|
|
|
|
<td style="background-color: silver; text-align: center;">(4 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: gray; text-align: center;">(4 bytes)</td>
|
|
|
|
<td style="background-color: gray; text-align: center;">FLP for Chunk 4
|
|
(4 bytes)</td>
|
|
|
|
<td style="background-color: silver; text-align: center;" rowspan="2">
|
|
Chunk 4 (8 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: silver; text-align: center;">(4 bytes)</td>
|
|
|
|
<td style="background-color: silver; text-align: center;">(4 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: silver; text-align: center;">Pointer to
|
|
next Block (4 bytes)</td>
|
|
|
|
<td style="background-color: gray; text-align: center;">(4 bytes)</td>
|
|
|
|
<td style="background-color: gray; text-align: center;">Pointer to next
|
|
Block (4 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: gray; text-align: center;">Size of next
|
|
Block (4 bytes)</td>
|
|
|
|
<td style="background-color: silver; text-align: center;">Size of next
|
|
Block (4 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: red; text-align: center;" colspan="4">
|
|
Memory not belonging to process</td>
|
|
</tr>
|
|
</table>
|
|
|
|
<p>Finally, here is a convoluted example where the requested_size is 7,
|
|
sizeof(void *) == 3, and sizeof(size_type) == 5, showing how the least
|
|
common multiple guarantees alignment requirements even in the oddest of
|
|
circumstances:</p>
|
|
|
|
<table cellspacing="0" cellpadding="0" border="3" style="clear: both;"
|
|
align="center" summary="">
|
|
<caption>
|
|
<em>Memory block containing 2 chunks, showing overlying array structures</em>
|
|
</caption>
|
|
|
|
<tr>
|
|
<th>Sections</th>
|
|
|
|
<th>size_type alignment</th>
|
|
|
|
<th>void * alignment</th>
|
|
|
|
<th>requested_size alignment</th>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: red; text-align: center;" colspan="4">
|
|
Memory not belonging to process <!-- First Section --></td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: gray; text-align: center;" rowspan="42">
|
|
Chunks section (210 bytes)</td>
|
|
|
|
<td style="background-color: gray; text-align: center;">(5 bytes)</td>
|
|
|
|
<td style="background-color: gray; text-align: center;" rowspan="3">
|
|
Interleaved free list pointer for Chunk 1 (15 bytes; 3 used)</td>
|
|
|
|
<td style="background-color: gray; text-align: center;" rowspan="21">
|
|
Chunk 1 (105 bytes; 7 used)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: silver; text-align: center;">(5 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: gray; text-align: center;">(5 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: silver; text-align: center;">(5 bytes)</td>
|
|
|
|
<td style="background-color: silver; text-align: center;" rowspan="3">
|
|
(15 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: gray; text-align: center;">(5 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: silver; text-align: center;">(5 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: gray; text-align: center;">(5 bytes)</td>
|
|
|
|
<td style="background-color: gray; text-align: center;" rowspan="3">(15
|
|
bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: silver; text-align: center;">(5 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: gray; text-align: center;">(5 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: silver; text-align: center;">(5 bytes)</td>
|
|
|
|
<td style="background-color: silver; text-align: center;" rowspan="3">
|
|
(15 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: gray; text-align: center;">(5 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: silver; text-align: center;">(5 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: gray; text-align: center;">(5 bytes)</td>
|
|
|
|
<td style="background-color: gray; text-align: center;" rowspan="3">(15
|
|
bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: silver; text-align: center;">(5 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: gray; text-align: center;">(5 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: silver; text-align: center;">(5 bytes)</td>
|
|
|
|
<td style="background-color: silver; text-align: center;" rowspan="3">
|
|
(15 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: gray; text-align: center;">(5 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: silver; text-align: center;">(5 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: gray; text-align: center;">(5 bytes)</td>
|
|
|
|
<td style="background-color: gray; text-align: center;" rowspan="3">(15
|
|
bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: silver; text-align: center;">(5 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: gray; text-align: center;">(5 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: silver; text-align: center;">(5 bytes)</td>
|
|
|
|
<td style="background-color: silver; text-align: center;" rowspan="3">
|
|
Interleaved free list pointer for Chunk 2 (15 bytes; 3 used)</td>
|
|
|
|
<td style="background-color: silver; text-align: center;" rowspan="21">
|
|
Chunk 2 (105 bytes; 7 used)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: gray; text-align: center;">(5 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: silver; text-align: center;">(5 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: gray; text-align: center;">(5 bytes)</td>
|
|
|
|
<td style="background-color: gray; text-align: center;" rowspan="3">(15
|
|
bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: silver; text-align: center;">(5 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: gray; text-align: center;">(5 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: silver; text-align: center;">(5 bytes)</td>
|
|
|
|
<td style="background-color: silver; text-align: center;" rowspan="3">
|
|
(15 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: gray; text-align: center;">(5 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: silver; text-align: center;">(5 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: gray; text-align: center;">(5 bytes)</td>
|
|
|
|
<td style="background-color: gray; text-align: center;" rowspan="3">(15
|
|
bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: silver; text-align: center;">(5 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: gray; text-align: center;">(5 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: silver; text-align: center;">(5 bytes)</td>
|
|
|
|
<td style="background-color: silver; text-align: center;" rowspan="3">
|
|
(15 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: gray; text-align: center;">(5 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: silver; text-align: center;">(5 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: gray; text-align: center;">(5 bytes)</td>
|
|
|
|
<td style="background-color: gray; text-align: center;" rowspan="3">(15
|
|
bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: silver; text-align: center;">(5 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: gray; text-align: center;">(5 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: silver; text-align: center;">(5 bytes)</td>
|
|
|
|
<td style="background-color: silver; text-align: center;" rowspan="3">
|
|
(15 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: gray; text-align: center;">(5 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: silver; text-align: center;">(5 bytes)
|
|
<!-- Second Section --></td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: silver; text-align: center;" rowspan="3">
|
|
Pointer to next Block (15 bytes; 3 used)</td>
|
|
|
|
<td style="background-color: gray; text-align: center;">(5 bytes)</td>
|
|
|
|
<td style="background-color: gray; text-align: center;" rowspan="3">
|
|
Pointer to next Block (15 bytes; 3 used)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: silver; text-align: center;">(5 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: gray; text-align: center;">(5 bytes)
|
|
<!-- Third Section --></td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: gray; text-align: center;">Size of next
|
|
Block (5 bytes; 5 used)</td>
|
|
|
|
<td style="background-color: silver; text-align: center;">Size of next
|
|
Block (5 bytes; 5 used)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: red; text-align: center;" colspan="4">
|
|
Memory not belonging to process</td>
|
|
</tr>
|
|
</table>
|
|
|
|
<h2>How Contiguous Chunks are Handled</h2>
|
|
|
|
<p>The theorem above guarantees all alignment requirements for allocating
|
|
chunks and also implementation details such as the interleaved free list.
|
|
However, it does so by adding padding when necessary; therefore, we have to
|
|
treat allocations of contiguous chunks in a different way.</p>
|
|
|
|
<p>Using array arguments similar to the above, we can translate any request
|
|
for contiguous memory for <em>n</em> objects of requested_size into a
|
|
request for <em>m</em> contiguous chunks. <em>m</em> is simply ceil(n *
|
|
requested_size / alloc_size), where alloc_size is the actual size of the
|
|
chunks. To illustrate:</p>
|
|
|
|
<p>Here's an example memory block, where requested_size == 1 and sizeof(void
|
|
*) == sizeof(size_type) == 4:</p>
|
|
|
|
<table cellspacing="0" cellpadding="0" border="3" style="clear: both;"
|
|
align="center" summary="">
|
|
<caption>
|
|
<em>Memory block containing 4 chunks; requested_size is 1</em>
|
|
</caption>
|
|
|
|
<tr>
|
|
<th>Sections</th>
|
|
|
|
<th>size_type alignment</th>
|
|
|
|
<th>void * alignment</th>
|
|
|
|
<th>requested_size alignment</th>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: red; text-align: center;" colspan="4">
|
|
Memory not belonging to process</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: gray; text-align: center;" rowspan="4">
|
|
Chunks section (16 bytes)</td>
|
|
|
|
<td style="background-color: gray; text-align: center;">(4 bytes)</td>
|
|
|
|
<td style="background-color: gray; text-align: center;">FLP to Chunk 2
|
|
(4 bytes)</td>
|
|
|
|
<td style="background-color: gray; text-align: center;">Chunk 1 (4
|
|
bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: silver; text-align: center;">(4 bytes)</td>
|
|
|
|
<td style="background-color: silver; text-align: center;">FLP to Chunk 3
|
|
(4 bytes)</td>
|
|
|
|
<td style="background-color: silver; text-align: center;">Chunk 2 (4
|
|
bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: gray; text-align: center;">(4 bytes)</td>
|
|
|
|
<td style="background-color: gray; text-align: center;">FLP to Chunk 4
|
|
(4 bytes)</td>
|
|
|
|
<td style="background-color: gray; text-align: center;">Chunk 3 (4
|
|
bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: silver; text-align: center;">(4 bytes)</td>
|
|
|
|
<td style="background-color: silver; text-align: center;">FLP to
|
|
end-of-list (4 bytes)</td>
|
|
|
|
<td style="background-color: silver; text-align: center;">Chunk 4 (4
|
|
bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: silver; text-align: center;">Pointer to
|
|
next Block (4 bytes)</td>
|
|
|
|
<td style="background-color: gray; text-align: center;">(4 bytes)</td>
|
|
|
|
<td style="background-color: gray; text-align: center;">Ptr to
|
|
end-of-list (4 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: gray; text-align: center;">Size of next
|
|
Block (4 bytes)</td>
|
|
|
|
<td style="background-color: silver; text-align: center;">0 (4 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: red; text-align: center;" colspan="4">
|
|
Memory not belonging to process</td>
|
|
</tr>
|
|
</table>
|
|
<br>
|
|
<table cellspacing="0" cellpadding="0" border="3" style="clear: both;"
|
|
align="center" summary="">
|
|
<caption>
|
|
<em>After user requests 7 contiguous elements of requested_size</em>
|
|
</caption>
|
|
|
|
<tr>
|
|
<th>Sections</th>
|
|
|
|
<th>size_type alignment</th>
|
|
|
|
<th>void * alignment</th>
|
|
|
|
<th>requested_size alignment</th>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: red; text-align: center;" colspan="4">
|
|
Memory not belonging to process</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: gray; text-align: center;" rowspan="4">
|
|
Chunks section (16 bytes)</td>
|
|
|
|
<td style="background-color: gray; text-align: center;">(4 bytes)</td>
|
|
|
|
<td style="background-color: gray; text-align: center;">(4 bytes)</td>
|
|
|
|
<td style="background-color: gray; text-align: center;">4 bytes in use
|
|
by program</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: silver; text-align: center;">(4 bytes)</td>
|
|
|
|
<td style="background-color: silver; text-align: center;">(4 bytes)</td>
|
|
|
|
<td style="background-color: silver; text-align: center;">3 bytes in use
|
|
by program (1 byte unused)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: gray; text-align: center;">(4 bytes)</td>
|
|
|
|
<td style="background-color: gray; text-align: center;">FLP to Chunk 4
|
|
(4 bytes)</td>
|
|
|
|
<td style="background-color: gray; text-align: center;">Chunk 3 (4
|
|
bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: silver; text-align: center;">(4 bytes)</td>
|
|
|
|
<td style="background-color: silver; text-align: center;">FLP to
|
|
end-of-list (4 bytes)</td>
|
|
|
|
<td style="background-color: silver; text-align: center;">Chunk 4 (4
|
|
bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: silver; text-align: center;">Pointer to
|
|
next Block (4 bytes)</td>
|
|
|
|
<td style="background-color: gray; text-align: center;">(4 bytes)</td>
|
|
|
|
<td style="background-color: gray; text-align: center;">Ptr to
|
|
end-of-list (4 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: gray; text-align: center;">Size of next
|
|
Block (4 bytes)</td>
|
|
|
|
<td style="background-color: silver; text-align: center;">0 (4 bytes)</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td style="background-color: red; text-align: center;" colspan="4">
|
|
Memory not belonging to process</td>
|
|
</tr>
|
|
</table>
|
|
|
|
<p>Then, when the user deallocates the contiguous memory, we can split it up
|
|
into chunks again.</p>
|
|
|
|
<p>Note that the implementation provided for allocating contiguous chunks
|
|
uses a linear instead of quadratic algorithm. This means that it
|
|
<strong>may not find</strong> contiguous free chunks if the free list is not
|
|
ordered. Thus, it is recommended to always use an ordered free list when
|
|
dealing with contiguous allocation of chunks. (In the example above, if
|
|
Chunk 1 pointed to Chunk 3 pointed to Chunk 2 pointed to Chunk 4, instead of
|
|
being in order, the contiguous allocation algorithm would have failed to
|
|
find any of the contiguous chunks).</p>
|
|
<hr>
|
|
|
|
<p><a href="http://validator.w3.org/check?uri=referer"><img border="0" src=
|
|
"../../../../doc/images/valid-html401.png" alt="Valid HTML 4.01 Transitional"
|
|
height="31" width="88"></a></p>
|
|
|
|
<p>Revised
|
|
<!--webbot bot="Timestamp" s-type="EDITED" s-format="%d %B, %Y" startspan -->05 December, 2006<!--webbot bot="Timestamp" endspan i-checksum="38516" --></p>
|
|
|
|
<p><i>Copyright © 2000, 2001 Stephen Cleary (scleary AT jerviswebb DOT com)</i></p>
|
|
|
|
<p><i>Distributed under the Boost Software License, Version 1.0. (See
|
|
accompanying file <a href="../../../../LICENSE_1_0.txt">LICENSE_1_0.txt</a>
|
|
or copy at <a href=
|
|
"http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt</a>)</i></p>
|
|
</body>
|
|
</html>
|