-<sect1 id="manual.ext.allocator.bitmap" xreflabel="bitmap_allocator">
+<section xmlns="http://docbook.org/ns/docbook" version="5.0"
+ xml:id="manual.ext.allocator.bitmap" xreflabel="bitmap_allocator">
<?dbhtml filename="bitmap_allocator.html"?>
-<sect1info>
+<info><title>bitmap_allocator</title>
<keywordset>
<keyword>
ISO C++
allocator
</keyword>
</keywordset>
-</sect1info>
+</info>
+
-<title>bitmap_allocator</title>
<para>
</para>
-<sect2 id="allocator.bitmap.design">
-<title>Design</title>
+<section xml:id="allocator.bitmap.design"><info><title>Design</title></info>
+
<para>
As this name suggests, this allocator uses a bit-map to keep track
- of the used and unused memory locations for it's book-keeping
+ of the used and unused memory locations for its book-keeping
purposes.
</para>
<para>
layer.
</para>
-</sect2>
+</section>
-<sect2 id="allocator.bitmap.impl">
-<title>Implementation</title>
+<section xml:id="allocator.bitmap.impl"><info><title>Implementation</title></info>
-<sect3 id="bitmap.impl.free_list_store" xreflabel="Free List Store">
- <title>Free List Store</title>
+
+<section xml:id="bitmap.impl.free_list_store" xreflabel="Free List Store"><info><title>Free List Store</title></info>
+
<para>
The Free List Store (referred to as FLS for the remaining part of this
free list if it exists.
</para>
<para>
- Suppose the free list size has reached it's threshold, then the
+ Suppose the free list size has reached its threshold, then the
largest block from among those in the list and the new block will
be selected and given back to the OS. This is done because it
reduces external fragmentation, and allows the OS to use the
Currently, (3) is being used with a value of 36% Maximum wastage per
Super Block.
</para>
-</sect3>
+</section>
-<sect3 id="bitmap.impl.super_block" xreflabel="Super Block">
- <title>Super Block</title>
+<section xml:id="bitmap.impl.super_block" xreflabel="Super Block"><info><title>Super Block</title></info>
+
<para>
A super block is the block of memory acquired from the FLS from
getting / returning Super Bocks to and from the OS using operator new
as defined by the C++ standard.
</para>
-</sect3>
+</section>
-<sect3 id="bitmap.impl.super_block_data" xreflabel="Super Block Data">
- <title>Super Block Data Layout</title>
+<section xml:id="bitmap.impl.super_block_data" xreflabel="Super Block Data"><info><title>Super Block Data Layout</title></info>
+
<para>
Each Super Block will be of some size that is a multiple of the
number of Bits Per Block. Typically, this value is chosen as
(assume a 32-bit system where, size_t is a 32-bit entity).
</para>
-<table frame='all'>
+<table frame="all">
<title>Bitmap Allocator Memory Map</title>
-<tgroup cols='5' align='left' colsep='1' rowsep='1'>
-<colspec colname='c1'></colspec>
-<colspec colname='c2'></colspec>
-<colspec colname='c3'></colspec>
-<colspec colname='c4'></colspec>
-<colspec colname='c5'></colspec>
+
+<tgroup cols="5" align="left" colsep="1" rowsep="1">
+<colspec colname="c1"/>
+<colspec colname="c2"/>
+<colspec colname="c3"/>
+<colspec colname="c4"/>
+<colspec colname="c5"/>
<tbody>
<row>
x 2,
which is 8-bytes, or 2 x sizeof(size_t).
</para>
-</sect3>
+</section>
-<sect3 id="bitmap.impl.max_wasted" xreflabel="Max Wasted Percentage">
- <title>Maximum Wasted Percentage</title>
+<section xml:id="bitmap.impl.max_wasted" xreflabel="Max Wasted Percentage"><info><title>Maximum Wasted Percentage</title></info>
+
<para>
This has nothing to do with the algorithm per-se,
create a function that returns the Max_Wastage_Percentage for us to use.
</para>
-</sect3>
+</section>
-<sect3 id="bitmap.impl.allocate" xreflabel="Allocate">
- <title><function>allocate</function></title>
+<section xml:id="bitmap.impl.allocate" xreflabel="Allocate"><info><title><function>allocate</function></title></info>
+
<para>
The allocate function is specialized for single object allocation
single object allocations.
</para>
-</sect3>
+</section>
-<sect3 id="bitmap.impl.deallocate" xreflabel="Deallocate">
- <title><function>deallocate</function></title>
+<section xml:id="bitmap.impl.deallocate" xreflabel="Deallocate"><info><title><function>deallocate</function></title></info>
+
<para>
The deallocate function again is specialized for single objects ONLY.
For all n belonging to > 1, the operator delete is called without
invariant is maintained by making sure that _S_last_request and
_S_last_dealloc_index point to valid locations within the vector.
</para>
-</sect3>
+</section>
-<sect3 id="bitmap.impl.questions" xreflabel="Questions">
- <title>Questions</title>
+<section xml:id="bitmap.impl.questions" xreflabel="Questions"><info><title>Questions</title></info>
+
- <sect4 id="bitmap.impl.question.1" xreflabel="Question 1">
- <title>1</title>
+ <section xml:id="bitmap.impl.question.1" xreflabel="Question 1"><info><title>1</title></info>
+
<para>
Q1) The "Data Layout" section is
cryptic. I have no idea of what you are trying to say. Layout of what?
32 x sizeof(value_type) x 2^n, where n ranges from 0 to 32 for 32-bit
systems.
</para>
- </sect4>
+ </section>
- <sect4 id="bitmap.impl.question.2" xreflabel="Question 2">
- <title>2</title>
+ <section xml:id="bitmap.impl.question.2" xreflabel="Question 2"><info><title>2</title></info>
+
<para>
And since I just mentioned the
term `each bitmap', what in the world is meant by it? What does each
whose exact number for a super-block of a given size I have just
mentioned.
</para>
- </sect4>
+ </section>
- <sect4 id="bitmap.impl.question.3" xreflabel="Question 3">
- <title>3</title>
+ <section xml:id="bitmap.impl.question.3" xreflabel="Question 3"><info><title>3</title></info>
+
<para>
How do the allocate and deallocate functions work in regard to
bitmaps?
The bit-map now looks like this:
1111111111111111111111111111111111111111111111111111111111111110
</para>
- </sect4>
-</sect3>
+ </section>
+</section>
-<sect3 id="bitmap.impl.locality" xreflabel="Locality">
- <title>Locality</title>
+<section xml:id="bitmap.impl.locality" xreflabel="Locality"><info><title>Locality</title></info>
+
<para>
Another issue would be whether to keep the all bitmaps in a
separate area in memory, or to keep them near the actual blocks
<orderedlist>
<listitem><para>Constant time access for the bitmap themselves, since no kind of
-look up will be needed to find the correct bitmap list or it's
+look up will be needed to find the correct bitmap list or its
equivalent.</para></listitem>
<listitem><para>And also this would preserve the cache as far as possible.</para></listitem>
</orderedlist>
single object allocations, though it preserves the locality of blocks
very well when they are returned back to the allocator.
</para>
-</sect3>
+</section>
-<sect3 id="bitmap.impl.grow_policy" xreflabel="Grow Policy">
- <title>Overhead and Grow Policy</title>
+<section xml:id="bitmap.impl.grow_policy" xreflabel="Grow Policy"><info><title>Overhead and Grow Policy</title></info>
+
<para>
Expected overhead per block would be 1 bit in memory. Also, once
the address of the free list has been found, the cost for
which can fit exactly in a CPU register. Hence, the term given is
exponential growth of the internal pool.
</para>
-</sect3>
+</section>
-</sect2>
+</section>
-</sect1>
+</section>
OSDN Git Service
