Notes - detailed explanation of space Configurator

Space Configurator

1. What is a space configurator

Efficient management of space (space application and recycling) for each container

2. Why do I need a space configurator

Various containers ----- > can store elements ----- > the bottom layer needs space

new application space

  1. operator new ---->malloc
  2. Call constructor ---- complete the construction of the object

Dynamic memory management summary

In the front container, new is used every time you open up space, but there are some disadvantages in using new

  • Space application and release need to be managed by the user, which is easy to cause memory leakage
  • Frequently apply for small memory blocks from the system, which is easy to cause memory fragments, such as nodes
  • Frequently apply to the system for a small amount of memory, which affects the running efficiency of the program
  • Malloc and new are directly used for application. There is a waste of extra space in front of each space (malloc will add new things before and after the applied space)
  • How to deal with the failure of applying for space
  • The code structure is chaotic and the code reuse rate is not high
  • Thread safety is not considered

Efficient memory management

3. How to implement SGI – STL space Configurator

Small memory

  1. Greater than 128 bytes ----- > large memory
  2. 128 bytes or less ----- > small memory
  • The primary space configurator handles large blocks of memory,
  • The secondary space configurator handles small chunks of memory.

Primary space Configurator

malloc+free----->set_new_handle

_malloc_alloc_template:

Application space

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(nullptr == result)
		result = oom_malloc(n);
	return result;
}

Free up space

static void deallocate(void *p, size_t /* n */)
{ 
	free(p);
}

Processing after malloc failure oom_malloc

  1. Accept function pointer (call set_new_handle)
  2. Verify that the function pointer is empty
    • Yes: throw exception directly
  3. Call the function corresponding to the function pointer
  4. Call malloc to continue applying for space
    • Successful application: return directly
    • Application failed: cycle continues
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);
	}
}

set_new_handle

Both the return value type and the parameter type are void * () function pointers

// 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);
}

Secondary space Configurator

Defects caused by frequent application of small memory blocks to the system
SGI-STL adopts the memory pool technology to improve the speed of applying for space and reduce the waste of additional space. It adopts the hash bucket method to improve the speed of obtaining space and efficient management.

Memory pool

Memory pool: first apply for a large memory block for standby. When memory is needed, go directly to the memory pool. When there is not enough space in the pool, get it from the memory. 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

char* _start,*finish

 

Application space

  1. Now find the appropriate block in the returned memory block
  2. Find ---- > whether to split ---- > do not need ---- > direct allocation
    You need to split the memory block
  3. Not found ----- > to apply in memory pool

Defects in application space

  1. Linked list to find the appropriate memory block, need to traverse, low efficiency
  2. division

Attention problem

  1. When users need space, can they intercept it directly from the large space in the memory pool? Why?
    A: choose from the linked list first and take it from the large block first. If the user needs a large block of space, he may not be able to give it
  2. Can the space returned by the user be directly spliced in front of a large block of memory?
    A: No
  3. How to manage the space returned by users?
    Answer: linked with a linked list
  4. What are the consequences of continuous cutting?
    Answer: memory fragmentation

Design of secondary space Configurator

The secondary space configurator in SGI-STL uses the memory pool technology, but does not use the linked list method to manage the space returned by the user (because it is inefficient for the user to find a suitable small memory when applying for space), but uses the hash bucket method for management, which is more efficient. Do you need 128 barrels of space to manage the memory blocks returned by users? The answer is no, because the space applied by users is basically an integer multiple of 4, and 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

Multiples of 4 for 32-bit systems
Multiples of 8 for 64 bit systems

There must be a pointer in each linked list. The 32-bit pointer is 4 bytes and the 64 bit pointer is 8 bytes

template <int inst>
class __default_alloc_template
{
private:
	enum { __ALIGN = 8 }; // If the memory required by the user is not an integer multiple of 8, align up to an integer multiple of 8
	enum { __MAX_BYTES = 128 }; // Dividing line between large and small memory blocks
	enum { __NFREELISTS = __MAX_BYTES / __ALIGN }; // The number of buckets required to save a small amount of memory in a hash bucket
	// If the memory block required by the user is not an integer multiple of 8, align it up to an integer multiple of 8
	static size_t ROUND_UP(size_t bytes)
	{
		return (((bytes)+__ALIGN - 1) & ~(__ALIGN - 1));
	}
private:
	// Maintain the linked list structure with a consortium ---- students can think about why there is no structure here
	union obj
	{
		union obj * free_list_link;
		char client_data[1]; /* The client sees this. */
	};
private:
	static obj * free_list[__NFREELISTS];
	// Hash function to find the corresponding bucket number according to the number of bytes provided by the user
	static size_t FREELIST_INDEX(size_t bytes)
	{
		return (((bytes)+__ALIGN - 1) / __ALIGN - 1);
	}
	// start_free and end_free is used to mark the beginning and end of large blocks of memory in the memory pool
	static char *start_free;
	static char *end_free;
	// It is used to record how many memory blocks the space configurator has requested from the system
	static size_t heap_size;
	// ... Cross platform operation, encapsulation lock, application space mode, etc
};

Management space of secondary space Configurator

void allocate(size_t n)
{
if(n>128)
; // Call the primary space Configurator
1. Calculate the bucket number with n
2. Check whether there are nodes (internal storage blocks) in the bucket
Yes: use the header deletion method to return the first memory block
No: return refill(Round_up(n));
}

void refill(size_t / is already an integer multiple of 8 /)
{
size_t nobjs =20;
char* chunk = chunk_alloc(n,nobjs);
if(nobjs == 1) / / just one piece
return chunk;
//1<nobjs<=20
Save the first memory and finally return it to external users
Hook the remaining nobjs-1 memory blocks into the corresponding bucket
}

void * chunk_alloc(size_t size,size_t& nobjs//20)
{
size_t totalBytes = nobjs*size;
size_t leftBytes = finish-start;

void * res =null;
If (leftbytes > = totalbytes) / / the memory pool has enough space to provide 20 bytes
{res = start;start+=totalBytes;return res;}
Else if (leftbytes > = size) / / at least one piece is provided if it is less than 20
{nobjs =leftBytes/size;res=start;start+=nobjssize;return res;}// How many pieces can you actually provide
else / / there is not enough space in the memory pool to provide even one piece
{
//1. Hook the remaining memory in the memory pool - > into the corresponding bucket
//total_get = 2total_bytes+RoundUP(heap_size>>4);
}
}

  1. Application space
// Function function: ask for space from space Configurator
// Parameter n: number of space bytes required by the user
// Return value: returns the first address of the space
static void * allocate(size_t n)
{
	obj * __VOLATILE * my_free_list;
	obj * __RESTRICT result;
	// Detect that the space required by the user is released more than 128 (i.e. whether it is a small memory)
	if (n > (size_t)__MAX_BYTES)
	{
		// Not a small block of memory, which is handled by the primary space configurator
		return (malloc_alloc::allocate(n));
	}
	// Find the corresponding bucket number according to the bytes required by the user
	my_free_list = free_list + FREELIST_INDEX(n);
	result = *my_free_list;
	// If there is no memory block in the bucket, add space to the bucket
	if (result == 0)
	{
		// Align n up to an integer of 8 to ensure that when the memory block is added to the bucket, the memory block must be an integer multiple of 8
		void *r = refill(ROUND_UP(n));
		return r;
	}
	// Maintain the chain relationship of the remaining memory blocks in the bucket
	*my_free_list = result->free_list_link;
	return (result);
};
  1.  

Recycle space


  1. There is no secondary space in the configuration
// Function function: the user returns the space to the space configurator
// Parameter: the first address of p space and the total size of n space
static void deallocate(void *p, size_t n)
{
	obj *q = (obj *)p;
	obj ** my_free_list;
	// If the space is not a small piece of memory, give it to the primary space configurator for recycling
	if (n > (size_t)__MAX_BYTES)	//If it exceeds 128, it shall be released according to the primary space configuration
	{
		malloc_alloc::deallocate(p, n);
		return;
	}
	//Less than 128
	// Find the corresponding hash bucket and hang the memory in the corresponding hash bucket
	my_free_list = free_list + FREELIST_INDEX(n);
	q->free_list_link = *my_free_list;
	*my_free_list = q;
}
  1. Replenish memory

template <int inst>
char* __default_alloc_template<inst>::chunk_alloc(size_t size, int& nobjs)
{
	// Calculate nobjs the total size of the size byte memory block and the total size of the remaining space in the memory pool
	char * result;
	size_t total_bytes = size * nobjs;
	size_t bytes_left = end_free - start_free;
	// If the memory pool can provide total_bytes, return
	if (bytes_left >= total_bytes)
	{
		result = start_free;
		start_free += total_bytes;
		return(result);
	}
	else if (bytes_left >= size)
	{
		// nobjs block cannot be provided, but at least one size byte memory block can be provided, which will be returned after being provided
		nobjs = bytes_left / size;
		total_bytes = size * nobjs;
		result = start_free;
		start_free += total_bytes;
		return(result);
	}
	else
	{
		// There is not enough memory pool space to provide even a small village
		// Ask the system heap for help and add space to the memory pool
		// Calculate the size of supplementary space to the memory: twice the total size of this time + apply to the system for the total size / 16
		size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
		// If the memory pool has remaining space (the space must be an integer multiple of 8), hang the space in the corresponding hash bucket
		if (bytes_left > 0)
		{
			// Find the matching hash bucket and hang the remaining space on it
			obj ** my_free_list = free_list + FREELIST_INDEX(bytes_left);
			((obj *)start_free)->free_list_link = *my_free_list;
			*my_ree_list = (obj *)start_free;
		}
		// Replenish space to the memory pool through the system heap. If the replenishment is successful, recursive allocation will continue
		start_free = (char *)malloc(bytes_to_get);
		if (0 == start_free)
		{
			// Failed to replenish space through the system heap. Check whether there are large memory blocks in the hash bucket
			int i;
			obj ** my_free_list, *p;
			for (i = size; i <= __MAX_BYTES; i += __ALIGN)
			{
				my_free_list = free_list + FREELIST_INDEX(i);
				p = *my_free_list;
				// If so, add the memory block into the memory pool and continue to allocate recursively
				if (0 != p)
				{
					*my_free_list = p->free_list_link;
					start_free = (char *)p;
					end_free = start_free + i;
					return(chunk_alloc(size, nobjs));
				}
			}
			// At the end of the mountain, you can only turn to the primary space configurator for help
			// Note: end must be used here_ Free is set to null, because once the primary space configurator throws an exception, there will be a problem
			end_free = 0;//end_free marks the end of the memory pool space
			start_free = (char *)malloc_alloc::allocate(bytes_to_get);
		}
		// Successfully replenish space to the memory pool through the system heap, update the information and continue to allocate
		heap_size += bytes_to_get;
		end_free = start_free + bytes_to_get;
		return(chunk_alloc(size, nobjs));
	}
}

Default selection for space Configurator

SGI-STL uses the primary or secondary space configurator by default, through USE_MALLOC macro control:

#ifdef __USE_MALLOC
	typedef malloc_alloc alloc;
	typedef malloc_alloc single_client_alloc;
#else
	// Secondary space configurator definition
#endif

At SGI_ This macro is not defined in STL, so: SGI by default_ STL uses a secondary space configurator

Re encapsulation of space Configurator

In C + +, the space required by the user may be of any type, including single object space and continuous space. It is not very friendly for the user to calculate the total size of the required space each time. Therefore, SGI-STL re encapsulates the space configurator:

template<class T, class Alloc>
class simple_alloc
{
public:
	// Apply for space of n T-type objects
	static T *allocate(size_t n)
	{
		return 0 == n ? 0 : (T*)Alloc::allocate(n * sizeof (T));
	}
	// Request a space of T-type object size
	static T *allocate(void)
	{
		return (T*)Alloc::allocate(sizeof (T));
	}
	// Free up space for n T-type object sizes
	static void deallocate(T *p, size_t n)
	{
		if (0 != n)
			Alloc::deallocate(p, n * sizeof (T));
	}
	// Free up space for the size of a T-type object
	static void deallocate(T *p)
	{
		Alloc::deallocate(p, sizeof (T));
	}
};

Object construction and release

For the sake of efficiency, SGI-STL decides to separate the two processes of space application release and object construction and deconstruction, because the destructor does not need to be called for the construction of some objects and the destructor does not need to be called during destruction. Separating this process can improve the performance of the program:

// When returning space, first call this function to clean up the resources in the object
template <class T>
inline void destroy(T* pointer)
{
	pointer->~T();
}
// Call this function after the space application is completed: use placement new to complete the object construction
template <class T1, class T2>
inline void construct(T1* p, const T2& value)
{
	new (p)T1(value);
}

 

  • The original form of this statement is: obj * * my_free_list, in that case * my_ free_ If a thread does not have a pointer in the memory optimized register, it may not be able to read the value of the other thread in the memory optimized register (if it does not have a pointer in the memory optimized register), so it may not be able to read the value of the other thread in the memory optimized register). To declare that a variable must be in memory, you need to modify it with volatile, where * my is modified_ free_list, it's free_list is an element in an array, not an array pointer, so volatile is placed between two *.

Tags: C++ data structure Interview computer

Posted by Wolf_22 on Sat, 14 May 2022 03:16:29 +0300