What is a space configurator?

Space configurator is used to efficiently manage space (space application and recycling) for each container

Why do I need a space configurator

Implement vector, list, map and unordered in simulation_ Map and other containers, all places that need space are applied through new
, although the code can run normally, it has the following shortcomings:

1. Space application and release need to be managed by the user, which is easy to cause memory leakage
2. Frequently apply for small memory from the system, which is easy to cause memory fragmentation
3. Frequently apply to the system for a small amount of memory, which affects the running efficiency of the program
4. malloc and new are directly used for application. There is a waste of extra space in front of each space
5. How to deal with the failure of applying for space
6. The code structure is chaotic and the code reuse rate is not high
7. Thread safety is not considered
   Therefore, an efficient memory management mechanism is needed to manage the application and recycling of space.

Taking 128 as the dividing line between small memory and large memory, the space configurator is divided into two-level structure. The first level space configurator handles large memory (greater than 128 bytes) and the second level space configurator handles small memory. (less than 128byte)

Primary space Configurator

The principle of the primary space configurator is very simple, that is, malloc and free are encapsulated at the bottom, and set is added_ new_ The idea of handler

	set_new_handler The function sets the new_p The function pointed to is new Operation or new[]Handler function called when the operation fails.

set_ new_ The function of the handler idea here is the processing mechanism after the malloc space application fails;

If the memory request fails:

1. If the programmer does not configure the processing function, the configurator will throw an exception by default;
2. If the programmer configures a handler, the configurator will process according to the handler.

Underlying code of primary space configurator:

template <int inst>
class __malloc_alloc_template
{
private:
	static void *oom_malloc(size_t);
public:
	 // Encapsulation of malloc
	static void * allocate(size_t n) 
	{
		// If the space application is successful, it will be returned directly. If it fails, it will be handed over to oom_malloc processing
		 void *result = malloc(n);
		 if (0 == result) 
		 result = oom_malloc(n);
		 return result; 
	}
	 // Encapsulation of free
	static void deallocate(void *p, size_t /* n */)
	{ free(p);}
	// Analog set_new_handle
	// The parameter of this function is a function pointer, and the return value type is also a function pointer
	// void (* set_malloc_handler( void (*f)() ) )()
	static void (* set_malloc_handler(void (*f)()))()
	{
		 void (* old)() = __malloc_alloc_oom_handler;
		 __malloc_alloc_oom_handler = f;
		 return(old);
	}
};
// This function is used when malloc fails to apply for space
template <int inst>
void * __malloc_alloc_template<inst>::oom_malloc(size_t n) 
{
	 void (* my_malloc_handler)();
	 void *result;
	 for (;;) 
	 {
		 // Check whether the user has set the Countermeasures for insufficient space. If not, throw exceptions and mode new
		 my_malloc_handler = __malloc_alloc_oom_handler;
		 if (0 == my_malloc_handler)
		 {
			 __THROW_BAD_ALLOC; 
		 }
	 
		 // If set, implement the countermeasures against insufficient space provided by the user
		 (*my_malloc_handler)();
	 
	 	// If you continue to apply for space, you may succeed
		 result = malloc(n);
		 if (result)
			 return(result);
	  }
  }
 typedef __malloc_alloc_template<0> malloc_alloc;

Secondary space Configurator

The secondary space configurator is specially responsible for processing small pieces of memory less than 128 bytes. The memory pool technology is used to improve the speed of applying for space and reduce the waste of additional space. The hash bucket method is used to improve the speed of space acquisition and efficient management.

Memory pool

First apply for a large memory block as a memory pool. When memory is needed, go directly to the memory pool. When the space in the pool is insufficient, go to the memory again. When the user doesn't use it, return it directly to the memory pool. It avoids the problems of low efficiency, memory fragmentation and additional waste caused by frequent application of small memory to the system.

working principle

First, apply for a memory pool as a backup. If allocation is needed, divide it from the memory pool and hang it in the hash bucket. Release it after use, and hang the memory in the hash bucket at the corresponding position again

How to allocate memory block size:
Because the space applied by users is basically an integer multiple of 4, space of other sizes is rarely used. Therefore, SGI-STL aligns the memory block requested by the user up to an integer multiple of 8

Application space:
If you want to apply for X byte memory now: first, check whether there is a memory object of appropriate size in the hash bucket. If there is, take it directly. If not, cut a piece of memory of X*20 size in the memory pool and take one. The remaining 19 are placed in the corresponding hash bucket. Next time, apply for X byte memory, which can be obtained directly in this hash bucket.

If the memory size applied here is not an integer multiple of 8, align it to an integer multiple of 8.

Free up space:
Release the memory object of X byte, find the hash location corresponding to x, and hang the memory object directly under the corresponding location

Memory fragmentation problem

External debris:
Now a large amount of memory has been lent back, and these memory blocks are discontinuous, which can not meet our new large memory application requirements. This is external fragmentation.

Internal debris:
If you apply to the memory pool for 1 byte of memory space, due to the underlying principle of the secondary space configurator, the minimum memory block that can be allocated is 8 byte s, then the remaining 7 byte s will be wasted, which is called internal fragmentation.

In order to solve the above memory fragmentation problem, the partner system and slab allocator are introduced.