[analysis of STL source code] summary note (4): behind the scenes hero allocator

00 Write it at the front

【STL Source analysis 】 Summary notes （3）：vector First time to know

In front for vector In the analysis of , We met allocator

template<class T,class Alloc=alloc>

Dispensers are present throughout all containers , Even if we don't use it when using individual containers , But the space configuration behind it is all due to the allocator .

Let's read it this time allocator Principle , Help us better understand STL.

01 malloc()

All allocations will eventually come to malloc()

stay c++ On the level of operator new(), The underlying layer also calls malloc()

The size you want is only fill So big , but malloc Will match some other necessary things .

So this means that the larger the application space , The smaller the proportion of additional things , The smaller the application space is, the larger the proportion is .

02 summary

Back to allocator The implementation of the , that allocator The bottom layer of should also be made up of malloc() Supported by .

First look at one VC Version of ：

Observe allocator class

class alloctor{
    ...
    pointer allocate(size_type n,const void *)
    	{return (Allocate((difference_type) n,(pointer)0));}
    void deallocate(pointer p,size_type n)
    	{operator delete(p)}
}

allocate Called Allocate

Look again Allocate

template <class T>inline
...Allocate(...){
    return ...operator new(...)
}
   

Also explains VC in allocator The bottom layer is to use malloc() and free() Realized .

1. Let's talk about why allocator We don't often use

   Because when allocating and freeing space , How many elements need to be declared , It can be defined during allocation , But I usually don't remember it when I release it , So it's hard to use .

2. image VC This implementation of the will also lead to a problem ： When the elements are small but many , The extra cost will not be great ？

   Of course it will . This will lead to a lot of extra expenses , In this case, a lot of space is wasted .
   
   

03 SGI STL Medium alloc

stay SGI STL The configurator in solves the problem we mentioned above . It is also different from the standard specification , Other distributors use allocator, and SGI STL The in is named alloc.

And it doesn't take any parameters .

For example, the standard writing is ：

vector<int,std::alloctor<int>>iv;

But use SGI STL allocator Just write it like this ：

vector<int,std:alloc>iv;

Although it doesn't meet the standard , But the practical use is not a big problem , Because the allocator will be specified at the bottom , For example, as mentioned at the beginning vector

template<class T,class Alloc=alloc>

stay c++ in , Memory allocation and deallocation are a coherent set of operations . such as ：

class Foo{...};
    Foo *pf = new Foo;
    delete pf;

there new An operation is a combination of two operations ：1. Configure memory 2. Construction object

delete Operation is also a combination of two operations ：1. Analytic object 2. Free memory

stay STL allocator Separate the operations of these two phases , It is divided into object construction and Deconstruction and space configuration and release .

The file structure is as follows ：

#include <stl_alloc.h>// Responsible for the configuration and release of memory space 
#inlcude <stl_construct.h>// Responsible for the construction and Deconstruction of object content 
#inlcude <stl_uninitialized.h>// Some global functions are defined , Used to copy and fill large blocks of memory 

We are in front of vector The basic tools encountered for processing memory are defined in stl_uninitialized.h Inside

04 The construction and analysis of objects ：construct()&destroy()

construct()

The implementation of constructor is relatively simple ：

template <class T1,class T2>
inline void construct(T1 *p,const T2& value){
    new (p) T1 (value);
}

The function is to set the initial value value Set to the space pointed to by the pointer .

destroy()

Destructors have two versions .

The first version ：

template <class T>
inline void destroy(T* pointer){
    point->~T();
}

It's easy to understand , Directly destruct the object pointed to by the pointer .

The second version wants to destruct iterators [first,last) Objects in scope , There are some cases of judgment ：

template <class ForwardIterator>
inline void destroy(ForwardIterator first,ForwardIterator last){//1
    _destroy(first,last,value_type(first));
}

template <class ForwardIterator,class T>
inline void _destroy(ForwardIterator first,ForwardIterator last,T*){//2
    typedef typename _type_traits<T>::has_trivial_destructor trivial_destructor;
    _destroy_aux(first,last,trivial_destructor());
}

template <class ForwardIterator>
inline void _destroy_aux(ForwardIterator first, ForwardIterator last,_false_type){//3
    for(;first<last;++first)
        destroy(&*first);
}

template <class ForwardIterator>
inline void _destroy_aux(ForwardIterator first, ForwardIterator last,_true_type){}//4

Let's read this passage “ Dolls ” Code .

The first thing to know is this trivial destructor. Because what we want to destruct is a range , If the destructor of each of these objects is not important , So it's called trivial destructor.

So we want to know if we need to destruct , This avoids repeated calls to .

1. Here use value_type() To get the type of the object the iterator refers to
2. recycling _type_traits To determine whether a destructor is required . This call has_trivial_destructor To determine whether it is trivial destructor
3. If it is false_type, Then we need to destruct
4. If it is true_type, So it doesn't need to be destructed , Direct null operation

## 05 Allocation and release of space ：alloc

It shows alloc Ingenious design , It also solves the memory problem we mentioned earlier .

Considering that small blocks may cause memory fragmentation ,SGI A two-layer configurator is designed .

The first level configurator uses the common direct use malloc() and free() Methods .

The second level configurator adopts different strategies according to the situation ： When the configuration block exceeds 128bytes when , Call the first level configurator ; When the configuration block is less than 128bytes when , use memory pool Sort it out .

First level configurator

The first level configurator is defined as __malloc_alloc_template

Because the code is long , We discussed what the first level configurator did .

static void allocate(...){
     Use it directly malloc();
     When the requirements cannot be met, use oom_malloc();
}

static void deallocate(...){
     Use it directly free();
}

static void reallocate(...){
     Use it directly realloc();
     When the requirements cannot be met, use oom_realloc();
}

static void (*set_malloc_handler(...)){...}// Simulation c++set_new_handler Mechanism 

oom_malloc(),oom_realloc() Are used to deal with the situation of insufficient memory , Internal will keep trying to free memory , Try the configuration again .（ call set_malloc_handler)

set_malloc_handler Be similar to c++ Medium set_new_handler Mechanism , That is, you can ask the system to call a function you specify when the memory configuration requirements cannot be met , That is, call the processing routine specified by the client before throwing the exception .

because c++ Not provided realloc() Memory configuration , So we need to simulate a set_malloc_handler()

oom_malloc(),oom_realloc() Just keep trying to call the client specified processing routine we mentioned earlier . Of course, if not set , Will throw bad_alloc Abnormal information .（ As long as it is strictly observed new Corresponding delete There will be no problem with the operation of ）

Second level configurator

Second level configurator we need to focus on less than 128bytes Treatment method . This is also the key to solving the memory fragmentation problem .

The basic principle is to configure one block of memory at a time , And maintain its free linked list （free-lists）, The next requirement can be directly extracted from the free linked list . If the client returns a small block , Take it back .

The second level configurator will actively increase the memory demand of small blocks to 8 Multiple . For example, the demand is 30bytes, It will automatically adjust to 32bytes. The linked list maintains a size of 8 A block of multiples of , Take it out when you need it .

At the same time maintain 16 individual free-lists, Respectively 8,16,24,32,40,48,56,64,72,80,88,96,104,112,120,128.（ That's right 8 Of 1 To 16 times ）

The main implementation is as follows ：

template <bool threads ,int inst>
class _default_alloc_template{
    private:
    	static size_t ROUND_UP(size_t bytes){// take bytes Up to 8 Multiple 
            ...
        }
    
    private:
    	union obj{//free-list Node construction 
            union obj *free_list_link;
    	char client_data[1];
        };
    
    private:
    	static obj * volatile free_list[_NFREELIST];
    	static size_t FREELIST_INDEX(size_t bytes){...}// Decide to use the second n Number free-list
    
    private:
    	static void *refill(size_t n);// No blocks available to refill 
    	static char *chunk_alloc(size_t size,int &nobjs);
    
    public:
    	static void * allocate(size_t n){...}
    	static void dellocate(void *p,size_t n){...}
    	static void * reallocate(void *p,size_t old_sz,size_t new_size);
    	
};

The main content is related operations of space configuration .

allocate()

This function first determines the block size , Greater than 128bytes Call the first level configurator , Less than 128bytes Just use free-list, Use the available blocks , If not, increase the size to 8 Multiple boundary , Call again refill()

For example, the example above , First, according to the size 96bytes find free-list[11], Then assign the dereference value to result, Finally, readjust the link relationship , Back again result.

static  void* allocate(size_t n){
    obj *volatile *my_free_list;
    obj *result;
    
    if(n>(size_t)_MAX_BYTES){
        return (malloc_alloc::allocate(n));// Call the first level configurator 
    }
    
    my_free_list=free_list+FREELIST_INDEX(n);// seek 16 individual free-list A suitable one in 
    result=*my_free_list;
    if(result==0){// Not available , Refill 
        void * r=refill(ROUND_UP(n));
    }
    
    *my_free_list=result->free_list_link;// To readjust free-list, Point to the next block 
    return (result);
    
};

deallocate()

Recycling blocks means adding blocks to the linked list .

First let's q Point to the block to recycle , Then find the corresponding free-list, Then add the block to the linked list , Finally, adjust free-list.

static void deallocate(void *p,size_t n)
{
    obj *q=(obj*)p;
    obj *volatile *my_free_list;
    
    if(n>(size_t)_MAX_BYTES){
         (malloc_alloc::deallocate(p,n));
       	 return;// Call the first level configurator 
    }
    
    my_free_list=free_list+FREELIST_INDEX(n);// seek 16 individual free-list A suitable one in 
    q->free_list_link=*my_free_list;// Recycling blocks 
    *my_free_list=q;// adjustment free-list
}

refill()

When there is no available block, it will be refilled , The new block is taken from the memory pool , from chunk_alloc() complete .

Here's a brief note refill workflow :

refill(size_t n){
    int  block =20;
	 call chunk_alloc(), Try to get 20 Blocks as free-list The new node 

	if( Get only one block )
    	 Just assign this block to the caller ,free-list No new nodes 
	 otherwise free-list Prepare to incorporate new nodes 
    
	 stay chunk Build... In space free-list：
    	 The first 0 The block returns to the client 
    	 Start from the first block and string the nodes 
}

Memory pool

Take space from the memory pool to free-list Use yes chunk_alloc() What to do .

Say again chunk_alloc() workflow

chunk_alloc(size_t size,int &nobjs){
     First use end_free-start_free To determine the capacity of the memory pool 
    
    if( The memory pool space meets the requirements )
         Call out 20 Give me a block free-list
        
    else if( The memory pool space cannot meet the demand , However, one or more blocks can be supplied )
         How many calls there are , And then modify nobjs Is the actual value 
        
    else( The memory pool cannot even provide the size of a chunk ){
         If there is a little room left , You can find the right one first free-list And assign it 
      	 from heap Allocate memory in ：
             Allocate twice as much space as you need if enough （ There are additional quantities ）
             If it's not enough, take a look free-list Is there any unused space 
           	 Still no, only the first level configurator can be called , have a look out of memory Is there any way 
    }
        
     	
}

for instance ：

First call chunk_alloc(32,20), That is, fetch from the memory pool 20 individual 32bytes Space .

1. therefore malloc() To configure 40 individual 32bytes Block of . The first block is returned to the client , The rest is from free-list[3] maintain . Leave the rest to the memory pool （20 individual ）
2. Again = call chunk_alloc(64,20), That is, remove from the memory pool 20 individual 64bytes Space . Because now free-list[7] It's empty , Therefore, the memory pool is required to provide . The memory pool can only be used for （32*20）/64=10 individual . So the first block is returned to the client , The rest is by free-list[7] maintain . There is nothing left in the memory pool .
3. call chunk_alloc(96,20), That is, remove from the memory pool 20 individual 96bytes Space . because free-list[11] It's empty , The memory pool is empty , So we need to malloc()40+n( Additional quantity ) Of 96bytes block , It is also the first one to return to the client , Give the rest to free-list[11] maintain , The rest 20+n Managed by the memory pool .
4. 
   

06 summary

allocator More focus on 【 memory management 】 There will be a more detailed explanation at . I will not encounter it in the future allocator.

The key point is the processing method of the second level configurator , Need to master .