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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [libstdc++-v3/] [doc/] [xml/] [manual/] [bitmap_allocator.xml] - Blame information for rev 742

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 742 jeremybenn
2
         xml:id="manual.ext.allocator.bitmap" xreflabel="bitmap_allocator">
3
4
 
5
The bitmap_allocator
6
  
7
    
8
      ISO C++
9
    
10
    
11
      allocator
12
    
13
  
14
15
 
16
 
17
 
18
19
20
 
21
Design
22
 
23
 
24
  
25
    As this name suggests, this allocator uses a bit-map to keep track
26
    of the used and unused memory locations for its book-keeping
27
    purposes.
28
  
29
  
30
    This allocator will make use of 1 single bit to keep track of
31
    whether it has been allocated or not. A bit 1 indicates free,
32
    while 0 indicates allocated. This has been done so that you can
33
    easily check a collection of bits for a free block. This kind of
34
    Bitmapped strategy works best for single object allocations, and
35
    with the STL type parameterized allocators, we do not need to
36
    choose any size for the block which will be represented by a
37
    single bit. This will be the size of the parameter around which
38
    the allocator has been parameterized. Thus, close to optimal
39
    performance will result. Hence, this should be used for node based
40
    containers which call the allocate function with an argument of 1.
41
  
42
 
43
  
44
    The bitmapped allocator's internal pool is exponentially growing.
45
    Meaning that internally, the blocks acquired from the Free List
46
    Store will double every time the bitmapped allocator runs out of
47
    memory.
48
  
49
 
50
  
51
    The macro __GTHREADS decides whether to use
52
    Mutex Protection around every allocation/deallocation. The state
53
    of the macro is picked up automatically from the gthr abstraction
54
    layer.
55
  
56
 
57
58
 
59
Implementation
60
 
61
 
62
Free List Store
63
 
64
 
65
  
66
    The Free List Store (referred to as FLS for the remaining part of this
67
    document) is the Global memory pool that is shared by all instances of
68
    the bitmapped allocator instantiated for any type. This maintains a
69
    sorted order of all free memory blocks given back to it by the
70
    bitmapped allocator, and is also responsible for giving memory to the
71
    bitmapped allocator when it asks for more.
72
  
73
  
74
    Internally, there is a Free List threshold which indicates the
75
    Maximum number of free lists that the FLS can hold internally
76
    (cache).  Currently, this value is set at 64. So, if there are
77
    more than 64 free lists coming in, then some of them will be given
78
    back to the OS using operator delete so that at any given time the
79
    Free List's size does not exceed 64 entries. This is done because
80
    a Binary Search is used to locate an entry in a free list when a
81
    request for memory comes along.  Thus, the run-time complexity of
82
    the search would go up given an increasing size, for 64 entries
83
    however, lg(64) == 6 comparisons are enough to locate the correct
84
    free list if it exists.
85
  
86
  
87
    Suppose the free list size has reached its threshold, then the
88
    largest block from among those in the list and the new block will
89
    be selected and given back to the OS. This is done because it
90
    reduces external fragmentation, and allows the OS to use the
91
    larger blocks later in an orderly fashion, possibly merging them
92
    later. Also, on some systems, large blocks are obtained via calls
93
    to mmap, so giving them back to free system resources becomes most
94
    important.
95
  
96
  
97
    The function _S_should_i_give decides the policy that determines
98
    whether the current block of memory should be given to the
99
    allocator for the request that it has made. That's because we may
100
    not always have exact fits for the memory size that the allocator
101
    requests. We do this mainly to prevent external fragmentation at
102
    the cost of a little internal fragmentation. Now, the value of
103
    this internal fragmentation has to be decided by this function. I
104
    can see 3 possibilities right now. Please add more as and when you
105
    find better strategies.
106
  
107
 
108
109
  Equal size check. Return true only when the 2 blocks are of equal
110
size.
111
  Difference Threshold: Return true only when the _block_size is
112
greater than or equal to the _required_size, and if the _BS is > _RS
113
by a difference of less than some THRESHOLD value, then return true,
114
else return false. 
115
  Percentage Threshold. Return true only when the _block_size is
116
greater than or equal to the _required_size, and if the _BS is > _RS
117
by a percentage of less than some THRESHOLD value, then return true,
118
else return false.
119
120
 
121
  
122
    Currently, (3) is being used with a value of 36% Maximum wastage per
123
    Super Block.
124
  
125
126
 
127
Super Block
128
 
129
 
130
  
131
    A super block is the block of memory acquired from the FLS from
132
    which the bitmap allocator carves out memory for single objects
133
    and satisfies the user's requests. These super blocks come in
134
    sizes that are powers of 2 and multiples of 32
135
    (_Bits_Per_Block). Yes both at the same time!  That's because the
136
    next super block acquired will be 2 times the previous one, and
137
    also all super blocks have to be multiples of the _Bits_Per_Block
138
    value.
139
  
140
  
141
    How does it interact with the free list store?
142
  
143
  
144
    The super block is contained in the FLS, and the FLS is responsible for
145
    getting / returning Super Bocks to and from the OS using operator new
146
    as defined by the C++ standard.
147
  
148
149
 
150
Super Block Data Layout
151
 
152
  
153
    Each Super Block will be of some size that is a multiple of the
154
    number of Bits Per Block. Typically, this value is chosen as
155
    Bits_Per_Byte x sizeof(size_t). On an x86 system, this gives the
156
    figure 8 x 4 = 32. Thus, each Super Block will be of size 32
157
    x Some_Value. This Some_Value is sizeof(value_type). For now, let
158
    it be called 'K'. Thus, finally, Super Block size is 32 x K bytes.
159
  
160
  
161
    This value of 32 has been chosen because each size_t has 32-bits
162
    and Maximum use of these can be made with such a figure.
163
  
164
  
165
    Consider a block of size 64 ints. In memory, it would look like this:
166
    (assume a 32-bit system where, size_t is a 32-bit entity).
167
  
168
 
169
170
Bitmap Allocator Memory Map
171
 
172
173
174
175
176
177
178
 
179
180
  
181
    268
182
    0
183
    4294967295
184
    4294967295
185
    Data -> Space for 64 ints
186
  
187
188
189
190
 
191
  
192
    The first Column(268) represents the size of the Block in bytes as
193
    seen by the Bitmap Allocator. Internally, a global free list is
194
    used to keep track of the free blocks used and given back by the
195
    bitmap allocator.  It is this Free List Store that is responsible
196
    for writing and managing this information. Actually the number of
197
    bytes allocated in this case would be: 4 + 4 + (4x2) + (64x4) =
198
    272 bytes, but the first 4 bytes are an addition by the Free List
199
    Store, so the Bitmap Allocator sees only 268 bytes. These first 4
200
    bytes about which the bitmapped allocator is not aware hold the
201
    value 268.
202
  
203
 
204
  
205
  What do the remaining values represent?
206
  
207
    The 2nd 4 in the expression is the sizeof(size_t) because the
208
    Bitmapped Allocator maintains a used count for each Super Block,
209
    which is initially set to 0 (as indicated in the diagram). This is
210
    incremented every time a block is removed from this super block
211
    (allocated), and decremented whenever it is given back. So, when
212
    the used count falls to 0, the whole super block will be given
213
    back to the Free List Store.
214
  
215
  
216
    The value 4294967295 represents the integer corresponding to the bit
217
    representation of all bits set: 11111111111111111111111111111111.
218
  
219
  
220
    The 3rd 4x2 is size of the bitmap itself, which is the size of 32-bits
221
    x 2,
222
    which is 8-bytes, or 2 x sizeof(size_t).
223
  
224
225
 
226
Maximum Wasted Percentage
227
 
228
 
229
  
230
    This has nothing to do with the algorithm per-se,
231
    only with some vales that must be chosen correctly to ensure that the
232
    allocator performs well in a real word scenario, and maintains a good
233
    balance between the memory consumption and the allocation/deallocation
234
    speed.
235
  
236
  
237
    The formula for calculating the maximum wastage as a percentage:
238
  
239
 
240
  
241
(32 x k + 1) / (2 x (32 x k + 1 + 32 x c)) x 100.
242
  
243
 
244
  
245
    where k is the constant overhead per node (e.g., for list, it is
246
    8 bytes, and for map it is 12 bytes) and c is the size of the
247
    base type on which the map/list is instantiated. Thus, suppose the
248
    type1 is int and type2 is double, they are related by the relation
249
    sizeof(double) == 2*sizeof(int). Thus, all types must have this
250
    double size relation for this formula to work properly.
251
  
252
  
253
    Plugging-in: For List: k = 8 and c = 4 (int and double), we get:
254
    33.376%
255
  
256
 
257
  
258
For map/multimap: k = 12, and c = 4 (int and double), we get: 37.524%
259
  
260
  
261
    Thus, knowing these values, and based on the sizeof(value_type), we may
262
    create a function that returns the Max_Wastage_Percentage for us to use.
263
  
264
 
265
266
 
267
<function>allocate</function>
268
 
269
 
270
  
271
    The allocate function is specialized for single object allocation
272
    ONLY.  Thus, ONLY if n == 1, will the bitmap_allocator's
273
    specialized algorithm be used. Otherwise, the request is satisfied
274
    directly by calling operator new.
275
  
276
  
277
    Suppose n == 1, then the allocator does the following:
278
  
279
  
280
    
281
      
282
        Checks to see whether a free block exists somewhere in a region
283
        of memory close to the last satisfied request. If so, then that
284
        block is marked as allocated in the bit map and given to the
285
        user. If not, then (2) is executed.
286
    
287
    
288
    
289
      
290
        Is there a free block anywhere after the current block right
291
        up to the end of the memory that we have? If so, that block is
292
        found, and the same procedure is applied as above, and
293
        returned to the user. If not, then (3) is executed.
294
    
295
    
296
    
297
      
298
        Is there any block in whatever region of memory that we own
299
        free?  This is done by checking
300
      
301
      
302
        
303
        
304
        The use count for each super block, and if that fails then
305
        
306
        
307
        
308
        
309
          The individual bit-maps for each super block.
310
        
311
        
312
      
313
 
314
      
315
        Note: Here we are never touching any of the memory that the
316
        user will be given, and we are confining all memory accesses
317
        to a small region of memory! This helps reduce cache
318
        misses. If this succeeds then we apply the same procedure on
319
        that bit-map as (1), and return that block of memory to the
320
        user. However, if this process fails, then we resort to (4).
321
        
322
    
323
    
324
      
325
        This process involves Refilling the internal exponentially
326
        growing memory pool. The said effect is achieved by calling
327
        _S_refill_pool which does the following:
328
      
329
      
330
        
331
          
332
            Gets more memory from the Global Free List of the Required
333
            size.
334
          
335
        
336
      
337
      
338
      Adjusts the size for the next call to itself.
339
      
340
      
341
      
342
      
343
      Writes the appropriate headers in the bit-maps.
344
      
345
      
346
      
347
        
348
        Sets the use count for that super-block just allocated to 0
349
        (zero).
350
      
351
      
352
      
353
        
354
          All of the above accounts to maintaining the basic invariant
355
          for the allocator. If the invariant is maintained, we are
356
          sure that all is well. Now, the same process is applied on
357
          the newly acquired free blocks, which are dispatched
358
          accordingly.
359
      
360
      
361
    
362
    
363
364
 
365
366
Thus, you can clearly see that the allocate function is nothing but a
367
combination of the next-fit and first-fit algorithm optimized ONLY for
368
single object allocations.
369
370
 
371
372
 
373
<function>deallocate</function>
374
 
375
  
376
    The deallocate function again is specialized for single objects ONLY.
377
    For all n belonging to > 1, the operator delete is called without
378
    further ado, and the deallocate function returns.
379
  
380
  
381
    However for n == 1, a series of steps are performed:
382
  
383
 
384
  
385
    
386
      We first need to locate that super-block which holds the memory
387
      location given to us by the user. For that purpose, we maintain
388
      a static variable _S_last_dealloc_index, which holds the index
389
      into the vector of block pairs which indicates the index of the
390
      last super-block from which memory was freed. We use this
391
      strategy in the hope that the user will deallocate memory in a
392
      region close to what he/she deallocated the last time around. If
393
      the check for belongs_to succeeds, then we determine the bit-map
394
      for the given pointer, and locate the index into that bit-map,
395
      and mark that bit as free by setting it.
396
    
397
    
398
      If the _S_last_dealloc_index does not point to the memory block
399
      that we're looking for, then we do a linear search on the block
400
      stored in the vector of Block Pairs. This vector in code is
401
      called _S_mem_blocks. When the corresponding super-block is
402
      found, we apply the same procedure as we did for (1) to mark the
403
      block as free in the bit-map.
404
    
405
  
406
 
407
  
408
    Now, whenever a block is freed, the use count of that particular
409
    super block goes down by 1. When this use count hits 0, we remove
410
    that super block from the list of all valid super blocks stored in
411
    the vector.  While doing this, we also make sure that the basic
412
    invariant is maintained by making sure that _S_last_request and
413
    _S_last_dealloc_index point to valid locations within the vector.
414
  
415
416
 
417
Questions
418
 
419
 
420
  
1
421
 
422
    
423
Q1) The "Data Layout" section is
424
cryptic. I have no idea of what you are trying to say. Layout of what?
425
The free-list? Each bitmap? The Super Block?
426
    
427
    
428
      The layout of a Super Block of a given
429
size. In the example, a super block of size 32 x 1 is taken. The
430
general formula for calculating the size of a super block is
431
32 x sizeof(value_type) x 2^n, where n ranges from 0 to 32 for 32-bit
432
systems.
433
    
434
  
435
 
436
  
2
437
 
438
    
439
      And since I just mentioned the
440
term `each bitmap', what in the world is meant by it? What does each
441
bitmap manage? How does it relate to the super block? Is the Super
442
Block a bitmap as well?
443
    
444
    
445
      Each bitmap is part of a Super Block which is made up of 3 parts
446
      as I have mentioned earlier.  Re-iterating, 1. The use count,
447
      2. The bit-map for that Super Block. 3.  The actual memory that
448
      will be eventually given to the user. Each bitmap is a multiple
449
      of 32 in size. If there are 32 x (2^3) blocks of single objects
450
      to be given, there will be '32 x (2^3)' bits present.  Each 32
451
      bits managing the allocated / free status for 32 blocks. Since
452
      each size_t contains 32-bits, one size_t can manage up to 32
453
      blocks' status. Each bit-map is made up of a number of size_t,
454
      whose exact number for a super-block of a given size I have just
455
      mentioned.
456
    
457
  
458
 
459
  
3
460
 
461
    
462
      How do the allocate and deallocate functions work in regard to
463
      bitmaps?
464
    
465
    
466
      The allocate and deallocate functions manipulate the bitmaps and
467
      have nothing to do with the memory that is given to the user. As
468
      I have earlier mentioned, a 1 in the bitmap's bit field
469
      indicates free, while a 0 indicates allocated. This lets us
470
      check 32 bits at a time to check whether there is at lease one
471
      free block in those 32 blocks by testing for equality with
472
      (0). Now, the allocate function will given a memory block find
473
      the corresponding bit in the bitmap, and will reset it (i.e.,
474
      make it re-set (0)). And when the deallocate function is called,
475
      it will again set that bit after locating it to indicate that
476
      that particular block corresponding to this bit in the bit-map
477
      is not being used by anyone, and may be used to satisfy future
478
      requests.
479
    
480
    
481
      e.g.: Consider a bit-map of 64-bits as represented below:
482
      1111111111111111111111111111111111111111111111111111111111111111
483
    
484
 
485
    
486
      Now, when the first request for allocation of a single object
487
      comes along, the first block in address order is returned. And
488
      since the bit-maps in the reverse order to that of the address
489
      order, the last bit (LSB if the bit-map is considered as a
490
      binary word of 64-bits) is re-set to 0.
491
    
492
 
493
    
494
      The bit-map now looks like this:
495
      1111111111111111111111111111111111111111111111111111111111111110
496
    
497
  
498
499
 
500
Locality
501
 
502
  
503
    Another issue would be whether to keep the all bitmaps in a
504
    separate area in memory, or to keep them near the actual blocks
505
    that will be given out or allocated for the client. After some
506
    testing, I've decided to keep these bitmaps close to the actual
507
    blocks. This will help in 2 ways.
508
  
509
 
510
  
511
  Constant time access for the bitmap themselves, since no kind of
512
look up will be needed to find the correct bitmap list or its
513
equivalent.
514
  And also this would preserve the cache as far as possible.
515
  
516
 
517
  
518
    So in effect, this kind of an allocator might prove beneficial from a
519
    purely cache point of view. But this allocator has been made to try and
520
    roll out the defects of the node_allocator, wherein the nodes get
521
    skewed about in memory, if they are not returned in the exact reverse
522
    order or in the same order in which they were allocated. Also, the
523
    new_allocator's book keeping overhead is too much for small objects and
524
    single object allocations, though it preserves the locality of blocks
525
    very well when they are returned back to the allocator.
526
  
527
528
 
529
Overhead and Grow Policy
530
 
531
  
532
    Expected overhead per block would be 1 bit in memory. Also, once
533
    the address of the free list has been found, the cost for
534
    allocation/deallocation would be negligible, and is supposed to be
535
    constant time. For these very reasons, it is very important to
536
    minimize the linear time costs, which include finding a free list
537
    with a free block while allocating, and finding the corresponding
538
    free list for a block while deallocating. Therefore, I have
539
    decided that the growth of the internal pool for this allocator
540
    will be exponential as compared to linear for
541
    node_allocator. There, linear time works well, because we are
542
    mainly concerned with speed of allocation/deallocation and memory
543
    consumption, whereas here, the allocation/deallocation part does
544
    have some linear/logarithmic complexity components in it. Thus, to
545
    try and minimize them would be a good thing to do at the cost of a
546
    little bit of memory.
547
  
548
 
549
  
550
    Another thing to be noted is the pool size will double every time
551
    the internal pool gets exhausted, and all the free blocks have
552
    been given away. The initial size of the pool would be
553
    sizeof(size_t) x 8 which is the number of bits in an integer,
554
    which can fit exactly in a CPU register. Hence, the term given is
555
    exponential growth of the internal pool.
556
  
557
558
 
559
560
 
561

powered by: WebSVN 2.1.0

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