mt allocator documentation (draft)

[Paolo Carlini]

Stefan Olsson wrote:

> Looking forward to all comments...

Hi Stefan, I'm reading the doc and learning a lot from it!

A few cosmetic tid bits...

> Introduction
> ------------
> The mt allocator [hereinafter referred to simply as "the allocator"] 
> is a fixed
> size (power of two) allocator that was initially developed 
> specifically to suit
> the needs of multi threaded applications [hereinafter referred to as a MT
> application]. Over time the allocator has evolved and been improved in 
> many
> ways, one of the being that it now also does a good job in single 
> threaded
> applications [hereinafter referred to as a ST application].
> (Note: In this document, when referring to single threaded 
> applications this
> also includes applications that are compiled with gcc without thread 
> support
> enabled. This is accomplished using ifdef's on __GTHREADS)
>
> The aim of this document is to - from a application point of view - 
> describe
> the "inner workings" of the allocator.

I'm not native English speaker, but to me sounds much better: '... is to 
describe
- from a application point of view - the "inner workings"...'

> Initialization
> --------------
> The static variables (pointers to freelists, tuning parameters etc)
> are initialized to their default values at file scope, i.e.:

Missing blank line?

>  template<typename _Tp> size_t
>  __mt_alloc<_Tp>::_S_freelist_headroom = 10;
>
>The very first allocate() call will always call the _S_init() function. 
>In order to make sure that this function is called exactly once we make use
>of a __gthread_once (with _S_once_mt and _S_init as arguments) call in MT 
>applications and check a static bool (_S_initialized) in ST applications.
>
>The _S_init() function:
>- If the GLIBCXX_FORCE_NEW enviorment variable is set, it sets the bool
>  _S_force_new to true and then returns. This will cause subsequent calls to
>  allocate() to return memory directly from a new() call, and deallocate will
>  only do a delete() call.
>
>- In the GLIBCXX_FORCE_NEW enviorment variable is not set, both ST and MT
>
'If the...'

>  applications will:
>  - Calculate the number of bins needed. A bin is a specific power of two size
>    of bytes. I.e. By default the allocator will deal with requests of up to
>
Usually, I find (in books, papers): 'I.e., by default...'

>    128 bytes (or whatever the value of _S_max_bytes is when _S_init() is 
>    called). This means that there will be bins of the following sizes 
>    (in bytes): 1, 2, 4, 8, 16, 32, 64, 128. 
>
>  - Create the _S_binmap array. All requests are rounded up to the next 
>    "large enough" bin. I.e. A request for 29 bytes will cause a block from
>
Ditto.

>    the "32 byte bin" to be returned to the application. The purpose of 
>    _S_binmap is to speed up the process of finding out which bin to use. 
>    I.e. The value of _S_binmap[ 29 ] is initialized to 5 (bin 5 = 32 bytes).
>
Ditto.

>
>  - Create the _S_bin array. This array consists of bin_records. There will be
>    as many bin_records in this array as the number of bins that we calculated
>    erlier. I.e. If _S_max_bytes = 128 there will be 8 entries.
>
Ditto and 'earlier'.

>    Each bin_record is then initialized:
>    - bin_record->first = An array of pointers to block_records. There will be
>      as many block_records pointers as there are maximum number of threads 
>      (in a ST application there is only 1 thread, in a MT application there 
>      are _S_max_threads).
>      This holds the pointer to the first free block for each thread in this
>      bin. I.e. If we would like to know where the first free block of size 32
>
Ditto: this is the last one I explicitly mark.

[snip]

>A multi threaded example
>------------------------
>In the ST example we never used the thread_id variable present in each block. 
>Let's start by explaining the purpose of this in a MT application. 
>
>The concept of "ownership" was introduced since many MT applications allocate
>and deallocate memory to shared containers from different threads (such as a 
>cache shared amongst all threads). This introduces a problem if the allocator
>only returns memory to it's own freelist (I.e. there might be one thread doing
>
'... its own...'

[snip]

>The basic process of a deallocation call is simple; always add the block to the
>
Probably ':' instead of ';' is in case.

>end of the current threads freelist and update the counters and pointers (as
>described erlier with the specific check of ownership that causes the used 
>counter of the thread that originally allocated the block to be decreased
>instead of the current threads counter).
>
The last sentence is a little bit difficult to parse...

>And here comes the free and used counters to service. Each time a deallocation()
>call is made, the length of the current threads freelist is compared to the 
>amount memory in use by this thread. Let's go back to the example of an
>application that has one thread that does all the allocations and one that
>deallocates. Both these threads use say 516 32-byte blocks that was allocated
>during thread creation for example. Their used counters will both say 516 at
>this point. The allocation thread now grabs 1000 32-byte blocks and puts them
>in a shared container. The use counter for this thread is now 1516.
>The deallocation thread now deallocates 500 of these blocks. For each 
>deallocation made the used counter of the allocating thread is decreased and
>the freelist of the deallocation thread gets longer and longer. But the 
>calculation made in deallocate() will limit the length of the freelist in the
>deallocation thread to _S_freelist_headroom % of it's used counter. In this
>case, when the freelist (given that the _S_freelist_headroom is at it's default
>value of 10%) exceeds 52 (516/10) blocks will be returned to the global pool
>where the allocating thread may pick them up and reuse them. In order to 
>reduce lock contention (since this requires this bins mutex to be locked) this
>operation is also made in chunks of blocks (just like when chunks of blocks 
>are moved from the global freelist to a threads freelist mentioned above).
>
This heavy block could be split, perhaps...

That's all, for now!

Thanks,
Paolo.