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