OpenCores
URL https://opencores.org/ocsvn/openrisc_me/openrisc_me/trunk

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [gcc-4.5.1/] [libstdc++-v3/] [doc/] [html/] [manual/] [bitmap_allocator.html] - Blame information for rev 424

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 424 jeremybenn 
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
2 
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
3 
<html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>bitmap_allocator</title><meta name="generator" content="DocBook XSL Stylesheets V1.75.2" /><meta name="keywords" content="&#10;      ISO C++&#10;    , &#10;      allocator&#10;    " /><meta name="keywords" content="&#10;      ISO C++&#10;    , &#10;      library&#10;    " /><link rel="home" href="../spine.html" title="The GNU C++ Library Documentation" /><link rel="up" href="ext_allocators.html" title="Chapter 33. Allocators" /><link rel="prev" href="ext_allocators.html" title="Chapter 33. Allocators" /><link rel="next" href="ext_containers.html" title="Chapter 34. Containers" /></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">bitmap_allocator</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="ext_allocators.html">Prev</a> </td><th width="60%" align="center">Chapter 33. Allocators</th><td width="20%" align="right"> <a accesskey="n" href="ext_containers.html">Next</a></td></tr></table><hr /></div><div class="sect1" title="bitmap_allocator"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="manual.ext.allocator.bitmap"></a>bitmap_allocator</h2></div></div></div><p>
4 
</p><div class="sect2" title="Design"><div class="titlepage"><div><div><h3 class="title"><a id="allocator.bitmap.design"></a>Design</h3></div></div></div><p>
5 
    As this name suggests, this allocator uses a bit-map to keep track
6 
    of the used and unused memory locations for it's book-keeping
7 
    purposes.
8 
  </p><p>
9 
    This allocator will make use of 1 single bit to keep track of
10 
    whether it has been allocated or not. A bit 1 indicates free,
11 
    while 0 indicates allocated. This has been done so that you can
12 
    easily check a collection of bits for a free block. This kind of
13 
    Bitmapped strategy works best for single object allocations, and
14 
    with the STL type parameterized allocators, we do not need to
15 
    choose any size for the block which will be represented by a
16 
    single bit. This will be the size of the parameter around which
17 
    the allocator has been parameterized. Thus, close to optimal
18 
    performance will result. Hence, this should be used for node based
19 
    containers which call the allocate function with an argument of 1.
20 
  </p><p>
21 
    The bitmapped allocator's internal pool is exponentially growing.
22 
    Meaning that internally, the blocks acquired from the Free List
23 
    Store will double every time the bitmapped allocator runs out of
24 
    memory.
25 
  </p><p>
26 
    The macro <code class="literal">__GTHREADS</code> decides whether to use
27 
    Mutex Protection around every allocation/deallocation. The state
28 
    of the macro is picked up automatically from the gthr abstraction
29 
    layer.
30 
  </p></div><div class="sect2" title="Implementation"><div class="titlepage"><div><div><h3 class="title"><a id="allocator.bitmap.impl"></a>Implementation</h3></div></div></div><div class="sect3" title="Free List Store"><div class="titlepage"><div><div><h4 class="title"><a id="bitmap.impl.free_list_store"></a>Free List Store</h4></div></div></div><p>
31 
    The Free List Store (referred to as FLS for the remaining part of this
32 
    document) is the Global memory pool that is shared by all instances of
33 
    the bitmapped allocator instantiated for any type. This maintains a
34 
    sorted order of all free memory blocks given back to it by the
35 
    bitmapped allocator, and is also responsible for giving memory to the
36 
    bitmapped allocator when it asks for more.
37 
  </p><p>
38 
    Internally, there is a Free List threshold which indicates the
39 
    Maximum number of free lists that the FLS can hold internally
40 
    (cache).  Currently, this value is set at 64. So, if there are
41 
    more than 64 free lists coming in, then some of them will be given
42 
    back to the OS using operator delete so that at any given time the
43 
    Free List's size does not exceed 64 entries. This is done because
44 
    a Binary Search is used to locate an entry in a free list when a
45 
    request for memory comes along.  Thus, the run-time complexity of
46 
    the search would go up given an increasing size, for 64 entries
47 
    however, lg(64) == 6 comparisons are enough to locate the correct
48 
    free list if it exists.
49 
  </p><p>
50 
    Suppose the free list size has reached it's threshold, then the
51 
    largest block from among those in the list and the new block will
52 
    be selected and given back to the OS. This is done because it
53 
    reduces external fragmentation, and allows the OS to use the
54 
    larger blocks later in an orderly fashion, possibly merging them
55 
    later. Also, on some systems, large blocks are obtained via calls
56 
    to mmap, so giving them back to free system resources becomes most
57 
    important.
58 
  </p><p>
59 
    The function _S_should_i_give decides the policy that determines
60 
    whether the current block of memory should be given to the
61 
    allocator for the request that it has made. That's because we may
62 
    not always have exact fits for the memory size that the allocator
63 
    requests. We do this mainly to prevent external fragmentation at
64 
    the cost of a little internal fragmentation. Now, the value of
65 
    this internal fragmentation has to be decided by this function. I
66 
    can see 3 possibilities right now. Please add more as and when you
67 
    find better strategies.
68 
  </p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>Equal size check. Return true only when the 2 blocks are of equal
69 
size.</p></li><li class="listitem"><p>Difference Threshold: Return true only when the _block_size is
70 
greater than or equal to the _required_size, and if the _BS is &gt; _RS
71 
by a difference of less than some THRESHOLD value, then return true,
72 
else return false. </p></li><li class="listitem"><p>Percentage Threshold. Return true only when the _block_size is
73 
greater than or equal to the _required_size, and if the _BS is &gt; _RS
74 
by a percentage of less than some THRESHOLD value, then return true,
75 
else return false.</p></li></ol></div><p>
76 
    Currently, (3) is being used with a value of 36% Maximum wastage per
77 
    Super Block.
78 
  </p></div><div class="sect3" title="Super Block"><div class="titlepage"><div><div><h4 class="title"><a id="bitmap.impl.super_block"></a>Super Block</h4></div></div></div><p>
79 
    A super block is the block of memory acquired from the FLS from
80 
    which the bitmap allocator carves out memory for single objects
81 
    and satisfies the user's requests. These super blocks come in
82 
    sizes that are powers of 2 and multiples of 32
83 
    (_Bits_Per_Block). Yes both at the same time!  That's because the
84 
    next super block acquired will be 2 times the previous one, and
85 
    also all super blocks have to be multiples of the _Bits_Per_Block
86 
    value.
87 
  </p><p>
88 
    How does it interact with the free list store?
89 
  </p><p>
90 
    The super block is contained in the FLS, and the FLS is responsible for
91 
    getting / returning Super Bocks to and from the OS using operator new
92 
    as defined by the C++ standard.
93 
  </p></div><div class="sect3" title="Super Block Data Layout"><div class="titlepage"><div><div><h4 class="title"><a id="bitmap.impl.super_block_data"></a>Super Block Data Layout</h4></div></div></div><p>
94 
    Each Super Block will be of some size that is a multiple of the
95 
    number of Bits Per Block. Typically, this value is chosen as
96 
    Bits_Per_Byte x sizeof(size_t). On an x86 system, this gives the
97 
    figure 8 x 4 = 32. Thus, each Super Block will be of size 32
98 
    x Some_Value. This Some_Value is sizeof(value_type). For now, let
99 
    it be called 'K'. Thus, finally, Super Block size is 32 x K bytes.
100 
  </p><p>
101 
    This value of 32 has been chosen because each size_t has 32-bits
102 
    and Maximum use of these can be made with such a figure.
103 
  </p><p>
104 
    Consider a block of size 64 ints. In memory, it would look like this:
105 
    (assume a 32-bit system where, size_t is a 32-bit entity).
106 
  </p><div class="table"><a id="id620814"></a><p class="title"><b>Table 33.1. Bitmap Allocator Memory Map</b></p><div class="table-contents"><table summary="Bitmap Allocator Memory Map" border="1"><colgroup><col align="left" /><col align="left" /><col align="left" /><col align="left" /><col align="left" /></colgroup><tbody><tr><td align="left">268</td><td align="left">0</td><td align="left">4294967295</td><td align="left">4294967295</td><td align="left">Data -&gt; Space for 64 ints</td></tr></tbody></table></div></div><br class="table-break" /><p>
107 
    The first Column(268) represents the size of the Block in bytes as
108 
    seen by the Bitmap Allocator. Internally, a global free list is
109 
    used to keep track of the free blocks used and given back by the
110 
    bitmap allocator.  It is this Free List Store that is responsible
111 
    for writing and managing this information. Actually the number of
112 
    bytes allocated in this case would be: 4 + 4 + (4x2) + (64x4) =
113 
    272 bytes, but the first 4 bytes are an addition by the Free List
114 
    Store, so the Bitmap Allocator sees only 268 bytes. These first 4
115 
    bytes about which the bitmapped allocator is not aware hold the
116 
    value 268.
117 
  </p><p>
118 
  What do the remaining values represent?</p><p>
119 
    The 2nd 4 in the expression is the sizeof(size_t) because the
120 
    Bitmapped Allocator maintains a used count for each Super Block,
121 
    which is initially set to 0 (as indicated in the diagram). This is
122 
    incremented every time a block is removed from this super block
123 
    (allocated), and decremented whenever it is given back. So, when
124 
    the used count falls to 0, the whole super block will be given
125 
    back to the Free List Store.
126 
  </p><p>
127 
    The value 4294967295 represents the integer corresponding to the bit
128 
    representation of all bits set: 11111111111111111111111111111111.
129 
  </p><p>
130 
    The 3rd 4x2 is size of the bitmap itself, which is the size of 32-bits
131 
    x 2,
132 
    which is 8-bytes, or 2 x sizeof(size_t).
133 
  </p></div><div class="sect3" title="Maximum Wasted Percentage"><div class="titlepage"><div><div><h4 class="title"><a id="bitmap.impl.max_wasted"></a>Maximum Wasted Percentage</h4></div></div></div><p>
134 
    This has nothing to do with the algorithm per-se,
135 
    only with some vales that must be chosen correctly to ensure that the
136 
    allocator performs well in a real word scenario, and maintains a good
137 
    balance between the memory consumption and the allocation/deallocation
138 
    speed.
139 
  </p><p>
140 
    The formula for calculating the maximum wastage as a percentage:
141 
  </p><p>
142 
(32 x k + 1) / (2 x (32 x k + 1 + 32 x c)) x 100.
143 
  </p><p>
144 
    where k is the constant overhead per node (e.g., for list, it is
145 
    8 bytes, and for map it is 12 bytes) and c is the size of the
146 
    base type on which the map/list is instantiated. Thus, suppose the
147 
    type1 is int and type2 is double, they are related by the relation
148 
    sizeof(double) == 2*sizeof(int). Thus, all types must have this
149 
    double size relation for this formula to work properly.
150 
  </p><p>
151 
    Plugging-in: For List: k = 8 and c = 4 (int and double), we get:
152 
    33.376%
153 
  </p><p>
154 
For map/multimap: k = 12, and c = 4 (int and double), we get: 37.524%
155 
  </p><p>
156 
    Thus, knowing these values, and based on the sizeof(value_type), we may
157 
    create a function that returns the Max_Wastage_Percentage for us to use.
158 
  </p></div><div class="sect3" title="allocate"><div class="titlepage"><div><div><h4 class="title"><a id="bitmap.impl.allocate"></a><code class="function">allocate</code></h4></div></div></div><p>
159 
    The allocate function is specialized for single object allocation
160 
    ONLY.  Thus, ONLY if n == 1, will the bitmap_allocator's
161 
    specialized algorithm be used. Otherwise, the request is satisfied
162 
    directly by calling operator new.
163 
  </p><p>
164 
    Suppose n == 1, then the allocator does the following:
165 
  </p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>
166 
        Checks to see whether a free block exists somewhere in a region
167 
        of memory close to the last satisfied request. If so, then that
168 
        block is marked as allocated in the bit map and given to the
169 
        user. If not, then (2) is executed.
170 
    </p></li><li class="listitem"><p>
171 
        Is there a free block anywhere after the current block right
172 
        up to the end of the memory that we have? If so, that block is
173 
        found, and the same procedure is applied as above, and
174 
        returned to the user. If not, then (3) is executed.
175 
    </p></li><li class="listitem"><p>
176 
        Is there any block in whatever region of memory that we own
177 
        free?  This is done by checking
178 
      </p><div class="itemizedlist"><ul class="itemizedlist" type="disc"><li class="listitem"><p>
179 
        The use count for each super block, and if that fails then
180 
        </p></li><li class="listitem"><p>
181 
          The individual bit-maps for each super block.
182 
        </p></li></ul></div><p>
183 
        Note: Here we are never touching any of the memory that the
184 
        user will be given, and we are confining all memory accesses
185 
        to a small region of memory! This helps reduce cache
186 
        misses. If this succeeds then we apply the same procedure on
187 
        that bit-map as (1), and return that block of memory to the
188 
        user. However, if this process fails, then we resort to (4).
189 
        </p></li><li class="listitem"><p>
190 
        This process involves Refilling the internal exponentially
191 
        growing memory pool. The said effect is achieved by calling
192 
        _S_refill_pool which does the following:
193 
      </p><div class="itemizedlist"><ul class="itemizedlist" type="disc"><li class="listitem"><p>
194 
            Gets more memory from the Global Free List of the Required
195 
            size.
196 
          </p></li><li class="listitem"><p>
197 
      Adjusts the size for the next call to itself.
198 
      </p></li><li class="listitem"><p>
199 
      Writes the appropriate headers in the bit-maps.
200 
      </p></li><li class="listitem"><p>
201 
        Sets the use count for that super-block just allocated to 0
202 
        (zero).
203 
      </p></li><li class="listitem"><p>
204 
          All of the above accounts to maintaining the basic invariant
205 
          for the allocator. If the invariant is maintained, we are
206 
          sure that all is well. Now, the same process is applied on
207 
          the newly acquired free blocks, which are dispatched
208 
          accordingly.
209 
      </p></li></ul></div></li></ol></div><p>
210 
Thus, you can clearly see that the allocate function is nothing but a
211 
combination of the next-fit and first-fit algorithm optimized ONLY for
212 
single object allocations.
213 
</p></div><div class="sect3" title="deallocate"><div class="titlepage"><div><div><h4 class="title"><a id="bitmap.impl.deallocate"></a><code class="function">deallocate</code></h4></div></div></div><p>
214 
    The deallocate function again is specialized for single objects ONLY.
215 
    For all n belonging to &gt; 1, the operator delete is called without
216 
    further ado, and the deallocate function returns.
217 
  </p><p>
218 
    However for n == 1, a series of steps are performed:
219 
  </p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>
220 
      We first need to locate that super-block which holds the memory
221 
      location given to us by the user. For that purpose, we maintain
222 
      a static variable _S_last_dealloc_index, which holds the index
223 
      into the vector of block pairs which indicates the index of the
224 
      last super-block from which memory was freed. We use this
225 
      strategy in the hope that the user will deallocate memory in a
226 
      region close to what he/she deallocated the last time around. If
227 
      the check for belongs_to succeeds, then we determine the bit-map
228 
      for the given pointer, and locate the index into that bit-map,
229 
      and mark that bit as free by setting it.
230 
    </p></li><li class="listitem"><p>
231 
      If the _S_last_dealloc_index does not point to the memory block
232 
      that we're looking for, then we do a linear search on the block
233 
      stored in the vector of Block Pairs. This vector in code is
234 
      called _S_mem_blocks. When the corresponding super-block is
235 
      found, we apply the same procedure as we did for (1) to mark the
236 
      block as free in the bit-map.
237 
    </p></li></ol></div><p>
238 
    Now, whenever a block is freed, the use count of that particular
239 
    super block goes down by 1. When this use count hits 0, we remove
240 
    that super block from the list of all valid super blocks stored in
241 
    the vector.  While doing this, we also make sure that the basic
242 
    invariant is maintained by making sure that _S_last_request and
243 
    _S_last_dealloc_index point to valid locations within the vector.
244 
  </p></div><div class="sect3" title="Questions"><div class="titlepage"><div><div><h4 class="title"><a id="bitmap.impl.questions"></a>Questions</h4></div></div></div><div class="sect4" title="1"><div class="titlepage"><div><div><h5 class="title"><a id="bitmap.impl.question.1"></a>1</h5></div></div></div><p>
245 
Q1) The "Data Layout" section is
246 
cryptic. I have no idea of what you are trying to say. Layout of what?
247 
The free-list? Each bitmap? The Super Block?
248 
    </p><p>
249 
      The layout of a Super Block of a given
250 
size. In the example, a super block of size 32 x 1 is taken. The
251 
general formula for calculating the size of a super block is
252 
32 x sizeof(value_type) x 2^n, where n ranges from 0 to 32 for 32-bit
253 
systems.
254 
    </p></div><div class="sect4" title="2"><div class="titlepage"><div><div><h5 class="title"><a id="bitmap.impl.question.2"></a>2</h5></div></div></div><p>
255 
      And since I just mentioned the
256 
term `each bitmap', what in the world is meant by it? What does each
257 
bitmap manage? How does it relate to the super block? Is the Super
258 
Block a bitmap as well?
259 
    </p><p>
260 
      Each bitmap is part of a Super Block which is made up of 3 parts
261 
      as I have mentioned earlier.  Re-iterating, 1. The use count,
262 
      2. The bit-map for that Super Block. 3.  The actual memory that
263 
      will be eventually given to the user. Each bitmap is a multiple
264 
      of 32 in size. If there are 32 x (2^3) blocks of single objects
265 
      to be given, there will be '32 x (2^3)' bits present.  Each 32
266 
      bits managing the allocated / free status for 32 blocks. Since
267 
      each size_t contains 32-bits, one size_t can manage up to 32
268 
      blocks' status. Each bit-map is made up of a number of size_t,
269 
      whose exact number for a super-block of a given size I have just
270 
      mentioned.
271 
    </p></div><div class="sect4" title="3"><div class="titlepage"><div><div><h5 class="title"><a id="bitmap.impl.question.3"></a>3</h5></div></div></div><p>
272 
      How do the allocate and deallocate functions work in regard to
273 
      bitmaps?
274 
    </p><p>
275 
      The allocate and deallocate functions manipulate the bitmaps and
276 
      have nothing to do with the memory that is given to the user. As
277 
      I have earlier mentioned, a 1 in the bitmap's bit field
278 
      indicates free, while a 0 indicates allocated. This lets us
279 
      check 32 bits at a time to check whether there is at lease one
280 
      free block in those 32 blocks by testing for equality with
281 
      (0). Now, the allocate function will given a memory block find
282 
      the corresponding bit in the bitmap, and will reset it (i.e.,
283 
      make it re-set (0)). And when the deallocate function is called,
284 
      it will again set that bit after locating it to indicate that
285 
      that particular block corresponding to this bit in the bit-map
286 
      is not being used by anyone, and may be used to satisfy future
287 
      requests.
288 
    </p><p>
289 
      e.g.: Consider a bit-map of 64-bits as represented below:
290 
      1111111111111111111111111111111111111111111111111111111111111111
291 
    </p><p>
292 
      Now, when the first request for allocation of a single object
293 
      comes along, the first block in address order is returned. And
294 
      since the bit-maps in the reverse order to that of the address
295 
      order, the last bit (LSB if the bit-map is considered as a
296 
      binary word of 64-bits) is re-set to 0.
297 
    </p><p>
298 
      The bit-map now looks like this:
299 
      1111111111111111111111111111111111111111111111111111111111111110
300 
    </p></div></div><div class="sect3" title="Locality"><div class="titlepage"><div><div><h4 class="title"><a id="bitmap.impl.locality"></a>Locality</h4></div></div></div><p>
301 
    Another issue would be whether to keep the all bitmaps in a
302 
    separate area in memory, or to keep them near the actual blocks
303 
    that will be given out or allocated for the client. After some
304 
    testing, I've decided to keep these bitmaps close to the actual
305 
    blocks. This will help in 2 ways.
306 
  </p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>Constant time access for the bitmap themselves, since no kind of
307 
look up will be needed to find the correct bitmap list or it's
308 
equivalent.</p></li><li class="listitem"><p>And also this would preserve the cache as far as possible.</p></li></ol></div><p>
309 
    So in effect, this kind of an allocator might prove beneficial from a
310 
    purely cache point of view. But this allocator has been made to try and
311 
    roll out the defects of the node_allocator, wherein the nodes get
312 
    skewed about in memory, if they are not returned in the exact reverse
313 
    order or in the same order in which they were allocated. Also, the
314 
    new_allocator's book keeping overhead is too much for small objects and
315 
    single object allocations, though it preserves the locality of blocks
316 
    very well when they are returned back to the allocator.
317 
  </p></div><div class="sect3" title="Overhead and Grow Policy"><div class="titlepage"><div><div><h4 class="title"><a id="bitmap.impl.grow_policy"></a>Overhead and Grow Policy</h4></div></div></div><p>
318 
    Expected overhead per block would be 1 bit in memory. Also, once
319 
    the address of the free list has been found, the cost for
320 
    allocation/deallocation would be negligible, and is supposed to be
321 
    constant time. For these very reasons, it is very important to
322 
    minimize the linear time costs, which include finding a free list
323 
    with a free block while allocating, and finding the corresponding
324 
    free list for a block while deallocating. Therefore, I have
325 
    decided that the growth of the internal pool for this allocator
326 
    will be exponential as compared to linear for
327 
    node_allocator. There, linear time works well, because we are
328 
    mainly concerned with speed of allocation/deallocation and memory
329 
    consumption, whereas here, the allocation/deallocation part does
330 
    have some linear/logarithmic complexity components in it. Thus, to
331 
    try and minimize them would be a good thing to do at the cost of a
332 
    little bit of memory.
333 
  </p><p>
334 
    Another thing to be noted is the pool size will double every time
335 
    the internal pool gets exhausted, and all the free blocks have
336 
    been given away. The initial size of the pool would be
337 
    sizeof(size_t) x 8 which is the number of bits in an integer,
338 
    which can fit exactly in a CPU register. Hence, the term given is
339 
    exponential growth of the internal pool.
340 
  </p></div></div></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="ext_allocators.html">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="ext_allocators.html">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="ext_containers.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Chapter 33. Allocators </td><td width="20%" align="center"><a accesskey="h" href="../spine.html">Home</a></td><td width="40%" align="right" valign="top"> Chapter 34. Containers</td></tr></table></div></body></html>

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.