2. Space configurator (allocator)

code

All objects in the STL are stored in containers, and space configuration is taken care of by Allocator

The STL (SGI STL) provides two space configurators

  • std::allocUsed by default, with a lot of optimization
  • std::allocatorInefficient, just right::operator new 和 ::operator deleteSimple encapsulation of

2.1 std::allocator(Roughly as follows)

// defalloc.h
#ifndef DEFALLOC_H
#define DEFALLOC_H

#include<new>
#include<cstddef>
#include<cstdlib>
#include<climits>
#include<iostream>

using namespace std;

template <typename T>
inline T* allocate(ptrdiff_t size, T*){
	set_new_handler(0);
	T* tmp = (T*) (::operator new((size_t) (size * sizeof(T))));
	if(! tmp) {cerr<<"out of memory"<<endl;
		exit(1);
	}
	return tmp;
	
}

template <typename T>
inline void deallocate(T* buffer){
	::operator delete(buffer);
}

template <typename T>
class Allocator
{
	public:
		typedef T value_type;
		typedef T* pointer;
		typedef const T* const_pointer;
		typedef T& reference;
		typedef const T& const_reference;
		typedef size_t size_type;
		typedef ptrdiff_t difference_type;

		pointer allocate(size_type n){
			return ::allocate((difference_type) n, (pointer) 0);
		}

		void deallocate(pointer p) {::deallocate*p; }pointer address(reference x) {return(pointer) &x; }const_pointer const_address (const_reference x) {return(const_pointer) &x; }size_type init_page_size(a){
			return max(size_type(1), size_type(4096/sizeof(T)));
		}

		size_type max_size(a){
			return max(size_type(1), size_type(UINT_MAX/sizeof(T))); }};template <>
class Allocator <void>
{
	public:
		typedef void* pointer;	
};


#define DEFALLOC_H
#endif 
Copy the code

2.2 std::alloc

Separate the two steps of new and delete; Unnecessary configurations and releases can be reduced

  • stl_alloc.hResponsible for the configuration and release of memory space
  • stl_construct.hResponsible for object construction and destruction
  • stl_uninstialized.hDefines functions that handle memory globally

A rough implementation of stl_construct. H

// The stl_construct. H section is similar to the generic construct, and specialises char, wchar_t, pointer, and destroy for trival
// When the iterator version of destroy has a large scope, but the destructor for each object is not necessary, there is no need to call the destructor for each object
Traits are related, as described in chapter 3


#ifndef STL_CONSTRUCT_H
#define STL_CONSTRUCT_H

#include
       
         // To use placement new, an overload of new
       

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

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

template<typename ForwardIterator>
inline void destroy(ForwardIterator first, ForwardIterator last){
	__destroy(first, last, value_type(first));
}
// value_type see section 3.6, extract value_type for iterators

template<typename ForwardIterator, typename T>
inline void __destroy(ForwardIterator first, ForwardIterator last, T*){
	typedef typename __type_traits<T>::has_trivial_destructor trivial_destructor;
	__destroy_aux(first, last, trivial_destructor())
}

template<typename ForwardIterator>
inline void __destroy_aux(ForwardIterator first, ForwardIterator last, __false_type) {
	for(; first<last; ++first) destroy(*first); }template<typename ForwardIterator>
inline void __destroy_aux(ForwardIterator , ForwardIterator , __true_type){}

template<>
inline void destroy(char*, char*) {}

template<>
inline void destroy(wchar_t*, wchar_t*) {}

#endif
Copy the code

Stl_alloc.h Design policy

  • Requesting space from the System Heap, consider multithreading. Think about out of memory, think about memory fragmentation
  • Two-stage configurator
    • The first level is called directlymalloc.free(When the configured block is larger than 128bytes)
    • The second level, which depends on the policy (only the first level is used if __USE_MALLOC is defined), is managed by the memory pool and maintains 16 linked lists with different sizes of available space
      • Because of the small memory block, the smaller the memory block, the larger the proportion of space (linked list Pointers) used to store management information (the STL is addressed by the union structure (see the code below)template<bool threads, int inst> typename __default_alloc_template<threads, inst>::obj, is a pointer when not allocated, and becomes the corresponding data when allocated.)

The rough implementation of stl_alloc. H

// 由于并非直接调用new,会类似实现c++ new handler机制，类似set_new_handler(0)
#ifndef STL_ALLOC_H
#define STL_ALLOC_H

#if 0
#	include<new>
#	define __THROW_BAD_ALLOC throw bad_alloc
#elif !defined(__THROW_BAD_ALLOC)
#	include<iostream>
#	define __THROW_BAD_ALLOC std::cerr<<"out of memory"<<std::endl;
#endif
#include<cstdlib>
#include<new>

// ***一级malloc****
template<int inst>
class __malloc_alloc_template{
	private:
		static void *oom_malloc(size_t);
		static void *oom_realloc(void *, size_t);
		static void (* __malloc_alloc_oom_handler) (); // 实现c++ new handler
	public:
		static void *allocate(size_t n) {
			void *result = malloc(n);
			if (result==0) result=oom_malloc(n);
			return result;
		}

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

		static void *reallocate(void *p, size_t, size_t new_sz){
			void *result = realloc(p, new_sz);
			if (result==0) result=oom_realloc(p, new_sz);
			return result;
		}

		static void (*set_malloc_handler(void (*f)())) (){ //为啥不typedef 下?
			void (*old) () = __malloc_alloc_oom_handler;
			__malloc_alloc_oom_handler = f;
			return (old);
		}
};

template <int inst>
void (* __malloc_alloc_template<inst>::__malloc_alloc_oom_handler) ()=0; 

template<int inst>
void *__malloc_alloc_template<inst>::oom_malloc(size_t n) {
	void (*my_malloc_handler)();
	void *result;
	for (;;){
		my_malloc_handler = __malloc_alloc_oom_handler;   //内存不足处理
		if (my_malloc_handler==0) {__THROW_BAD_ALLOC;}
		my_malloc_handler();
		result = malloc(n);
		if (result) return result;
	}
}
template<int inst>
void *__malloc_alloc_template<inst>::oom_realloc(void *p, size_t n) {
	void (*my_malloc_handler)();
	void *result;
	for (;;){
		my_malloc_handler = __malloc_alloc_oom_handler;
		if (my_malloc_handler==0) {__THROW_BAD_ALLOC;}
		my_malloc_handler();
		result = realloc(p, n);
		if (result) return result;
	}
}
typedef __malloc_alloc_template<0> malloc_alloc;


enum {__ALIGN=8};
enum {__MAX_BYTE=128};
enum {__NFREELISTS=__MAX_BYTE / __ALIGN};

// ***二级malloc***
// 二级配置器维护了16个链表（free-list），分别管理8,16,24~128bytes的小额区块（对于需要分配的内存，会向上补全为8的倍数
template <bool threads, int inst>
class __default_alloc_template{
	private:
		static size_t ROUND_UP(size_t bytes){
			return (bytes + __ALIGN -1) & (__ALIGN-1);
		}

		union obj {
			union obj * free_list_link;
			char client_data[1];
		};

		static obj * volatile free_list[__NFREELISTS];
		static size_t FREELIST_INDEX(size_t bytes){
			return (bytes + __ALIGN-1)/(__ALIGN-1);
		}
		static void *refill(size_t);    //无可用free_list时调用，重新填充free_list，配置一块理论上nobjs个大小为传参的空间
		static char *chunk_alloc(size_t size,int &nobjs);  //从内存池获取内存的具体方法
		// chunk_alloc相关的内存池属性
		static char *start_free;
		static char *end_free;
		static size_t heap_size;
	public:
		static void *allocate(size_t n){
			/*大致逻辑就是大于128走一级分配
			 * 如果free_list中存在则取，并且更新链表
			 * 没有的话通过refill重新配置一大块区域
			 * */
			obj * volatile *my_free_list;
			obj *result;
			if (n>size_t(__MAX_BYTE)) {
				return malloc_alloc::allocate(n);
			}
			my_free_list = free_list + FREELIST_INDEX(n);
			result = *my_free_list;
			if (result==0){
				void *r=refill(ROUND_UP(n));
				return r;
			}
			*my_free_list = result->free_list_link;
			return result;
		}
		static void deallocate(void *p, size_t n) {
			obj *q=(obj *)p;
			obj *volatile *my_free_list;
			if (n>(size_t) __MAX_BYTE){
				malloc_alloc::deallocate(p, n);
				return;
			}
			my_free_list = free_list + FREELIST_INDEX(n);
			q->free_list_link = *my_free_list;
			*my_free_list = q;
		}
		static void *reallocate(void *p, size_t old_sz, size_t new_sz);
};
// static的一些初始化
template<bool threads, int inst>
char *__default_alloc_template<threads, inst>::start_free=0;
template<bool threads, int inst>
char *__default_alloc_template<threads, inst>::end_free=0;
template<bool threads, int inst>
size_t __default_alloc_template<threads, inst>::heap_size=0;

template<bool threads, int inst> 
typename __default_alloc_template<threads, inst>::obj *volatile 
__default_alloc_template<threads, inst>::free_list[__NFREELISTS]=
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};

template<bool threads, int inst>
void * __default_alloc_template<threads, inst>::refill(size_t n){
	int nobjs=20;
	obj * volatile *my_free_list;
	obj *result;
	obj *current_obj, *next_obj;
	int i;
	char *chunk = chunk_alloc(n, nobjs); //传的是int引用会更新
	if (1==nobjs) return (chunk); //只有一个的话不需要调整free_list
	my_free_list = free_list + FREELIST_INDEX(n);
	result = (obj *) chunk;
	*my_free_list = next_obj=(obj*) (chunk +n);
	for (i=1;;i++){
		current_obj = next_obj;
		next_obj = (obj*) (chunk +n);
		if (nobjs-1==i){
			current_obj->free_list_link=0;
			break;
		} else {
			current_obj->free_list_link=next_obj;
		}
	}
	return result;
}

template<bool threads, int inst>
char *
__default_alloc_template<threads, inst>::chunk_alloc(size_t size, int& nobjs){
	//一些分之递归调用自己是为了修正nobjs
	//涉及多线程的被忽略了
	char *result;
	size_t total_bytes=size*nobjs;
	size_t bytes_left = end_free-start_free;

	if (bytes_left>=total_bytes){
		result = start_free;
		start_free += total_bytes;
		return result;
	} else if (bytes_left >= size) {
		// 不能满足，但至少能提供一个
		nobjs = bytes_left/size;
		total_bytes = nobjs * size;
		result = start_free;
		start_free+=total_bytes;
		return result;
	} else {
		size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size>>4);
		if (bytes_left>0){
			//如果还有可用内存，先分配给free_list上小于其的最大链表维护的空间(可以优化)
			obj * volatile *my_free_list = free_list + FREELIST_INDEX(bytes_left);
			((obj *)start_free)->free_list_link = *my_free_list;
			*my_free_list = (obj *)start_free;
		}
		start_free = (char *) malloc(bytes_to_get);
		if (0==start_free){
			//如果heap无可用内存，尝试从更大的free_list上获取内存
			int i;
			obj *volatile *my_free_list, *p;
			for (i=size;i<=__MAX_BYTE;i+=__ALIGN){
				my_free_list = free_list + FREELIST_INDEX(i);
				p = *my_free_list;
				if (0!=p){
					*my_free_list=p->free_list_link;
					start_free = (char *) p;
					end_free = start_free+i;
					return chunk_alloc(size, nobjs);
				}
			}
			end_free = 0;
			start_free = (char *) malloc_alloc::allocate(bytes_to_get); //理论上会导致触发set_malloc_handler
		}
		heap_size += bytes_to_get;
		end_free = start_free + bytes_to_get;
		return chunk_alloc(size, nobjs);
	}
}

#endif
Copy the code