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