STL源码：空间配置器（三）内存的配置和释放、SGI的两级适配器

快来打我* 2022-08-07 07:44 141阅读 0赞

# 空间的配置与释放std::alloc #

之前了解了内存配置后的对象构造和内存释放前的对象析构行为，现在分析内存配置和释放。

对象构造前的空间配置和对象析构后的空间释放，由<stl\_alloc.h>负责，SGI对此的设计哲学如下：

1. 向 system heap 要求空间。

2. 考虑多线程（multi-threads）状态。

3. 考虑内存不足时的应变措施。

4. 考虑过多“小型区块”可能造成的内存碎片（fragment）问题。

考虑到小型区块所可能造成的内存破碎问题，**SGI设计了双层级配置器**，第一级配置器直接使用 malloc() 和 free() ,第二级配置器则视情况采用不同的策略：当配置区块超过 128 bytes时，视之为“足够大”，便调用第一级配置器；当配置区块小于 128 bytes时，视之为“过小”，为了降低额外负担，便采用复杂的 memory pool 整理方式，而不再求助于第一级配置器。

在SGI的整个设计究竟只开放第一级配置器，或是同时开放第二级配置器，取决于 \_\_USE\_MALLOC 是否被定义。

#ifdef  __USE_MALLOC
    ...
    typedef __malloc_alloc_template<0>  malloc_alloc;
    typedef malloc_alloc  alloc;  // 令 alloc 为第一级配置器
    #else
    ...
    // 令 alloc 为第二级配置器
    typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0>  alloc;
    #endif /* ! __USE_MALLOC */

\_\_malloc\_alloc\_template 就是第一级配置器，\_\_default\_alloc\_template 就是第二级配置器。SGI STL并未定义 \_\_USE\_MALLOC,所以SGI使用第二级配置器。

无论alloc被定义为第一级或第二级配置器， SGI 还为 alloc 包装了一个接口如下，使配置器的接口能够符合 STL 规格，其内部四个成员函数其实都是单纯的转调用，调用传递给配置器的成员函数。SGI STL容器全部使用这个 simple\_alloc 接口：

template<class T, class Alloc>
    class simple_alloc {
    
    public:
        static T *allocate(size_t n)
                    { return 0 == n? 0 : (T*) Alloc::allocate(n * sizeof (T)); }
        static T *allocate(void)
                    { return (T*) Alloc::allocate(sizeof (T)); }
        static void deallocate(T *p, size_t n)
                    { if (0 != n) Alloc::deallocate(p, n * sizeof (T)); }
        static void deallocate(T *p)
                    { Alloc::deallocate(p, sizeof (T)); }
    };

SGI STL容器全部使用这个simple\_alloc接口，例如：

template <class T, class Alloc = alloc>    //缺省使用alloc为配置器
    class vector {
       protected:
            //专属之空间配置器，每次配置一个元素大小
            typedef simple_alloc<value_type, Alloc> data_allocator;
    
             void deallocate() {
                if (...)
                     data_allocator::deallocate(start, end_of_storate - start);
             }
        ...
    };

# 第一级配置器\_\_malloc\_alloc\_template #

// 注意，无"template型别参数"。至于"非型别参数"inst，则完全没派上用场
    template <int inst>
    class __malloc_alloc_template {
    
    private:
    // 函数指针，以下函数将用来处理内存不足的情况
    //用于设置__malloc_alloc_oom_handler情况下循环分配内存，知道成功为止
    // oom : out of memory
    static void *oom_malloc(size_t);
    
    static void *oom_realloc(void *, size_t);
    
    //如果编译器支持模板静态成员，则使用错误处理函数，
    //类似C++的set_new_handler()，默认值为0，
    //如果不设置，则内存分配失败直接__THROW_BAD_ALLOC
     #ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
        static void (* __malloc_alloc_oom_handler)();
    #endif
    
    public:
    
    //分配指定大小的内存，如果分配失败，进入循环分配阶段
    //循环分配前提是保证正确设置了__malloc_alloc_oom_handler
    static void * allocate(size_t n)
    {
        void *result = malloc(n); // 第一级配置器直接使用 malloc()
        // 以下无法满足需求时，改用 oom_malloc()
        if (0 == result) result = oom_malloc(n);
        return result;
    }
    
    //后面的size_t是为了兼容operator delete
    static void deallocate(void *p, size_t /* n */)
    {
        free(p); // 第一级配置器直接使用 free()
    }
    
    //重新分配内存大小，第二个参数是为了兼容operator new
    static void * reallocate(void *p, size_t /* old_sz */, size_t new_sz)
    {
        void * result = realloc(p, new_sz); // 第一级配置器直接使用 realloc()
        // 以下无法满足需求时，改用 oom_realloc()
        if (0 == result) result = oom_realloc(p, new_sz);
        return result;
    }
    
    // 以下仿真C++的 set_new_handler()。换句话说，可以通过它
    // 指定你自己的 out-of-memory handler
    //设置错误处理函数，返回原来函数指针，不是C++标准规定的接口
    static void (* set_malloc_handler(void (*f)()))()
    {
        void (* old)() = __malloc_alloc_oom_handler;
        __malloc_alloc_oom_handler = f;
        return(old);
    }
    
    };
    
    // malloc_alloc out-of-memory handling
    #ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
    // 初值为 0。有待客端设定
    template <int inst>
    void (* __malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = 0;
    #endif
    
    <pre><span style="color:#008000;"> </span>//如果设置了__malloc_alloc_oom_handler,则首先执行错误处理，然后循环分配直到成功
    //如果未设置，__THROW_BAD_ALLOC
    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 (0 == my_malloc_handler) { __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 (0 == my_malloc_handler) { __THROW_BAD_ALLOC; }
            (*my_malloc_handler)(); // 调用处理例程，企图释放内存
            result = realloc(p, n); // 再次尝试配置内存
            if (result) return(result);
        }
    }
    
    // 注意，以下直接将参数 inst 指定为 0
    typedef __malloc_alloc_template<0> malloc_alloc;

**第一级配置器以 malloc()，free()，realloc()等 C 函数执行实际的内存配置、释放、重配置操作**，并实现出类似 C++ new-handler 的机制。（所谓 **C++ new handler 机制**是，你可以要求系统在内存配置需求无法被满足时，调用一个你所指定的函数。换句话说，一旦 ::operator new 无法完成任务，在丢出 std::bad\_alloc 异常状态之前，会先调用由客端指定的处理例程。）

使用“类似C++ new-handler机制”而不是直接运用该机制，因为它并非使用::operator new 来配置内存。

SGI第一级配置器的allocate()和realloc()都是在调用malloc()和realloc()不成功后，改调用oom\_malloc() 和oom\_realloc()。后两者都有内循环，不断调用“内存不足处理例程”，期望某次调用后，获得足够的内存而圆满完成任务。

# 第二级配置器 \_\_default\_alloc\_template #

第二级配置器多了一些机制，避免太多小额区块造成内存的碎片。小额区块带来的其实不仅是内存碎片，配置时的额外负担也是一个大问题。额外负担永远无法避免，毕竟系统要靠这多出来的空间来管理内存。但是区块越小，额外负担所占的比例越大，越显得浪费。如下图。

![Center][]

SGI第二级配置器做法是，**如果区块够大**，超过128bytes时，将移交第一级配置器处理。**当小于128bytes**，则以内存池管理，此法又称为次级配置：每次配置一大块内存，并维护对应之自由链表free-lists。下次若有相同大小的内存需求，直接从free-lists中拨出。如果客端释放小额块区，就由配置器回收到free-lists中——是的，别忘了，配置器除了负责配置，还负责回收。**为了方便管理，SGI第二级配置器主动将任何小额块区的内存需求量上调至8的倍数**（如，客端要求30bytes，则自动调整为32bytes），并**维护16个free-lists，各自分别管理大小为8、16、24、32、……、120、128bytes的小额块区**。

这种做法有两个优点： (1)**小对象的快速分配**。小对象是从内存池分配的，这个内存池是系统调用一次malloc分配一块足够大的区域给程序备用，当内存池耗尽时再向系统申请一块新的区域，整个过程类似于批发和零售，起先是由allocator向总经商批发一定量的货物，然后零售给用户，与每次都总经商要一个货物再零售给用户的过程相比，显然是快捷了。当然，这里的一个问题时，内存池会带来一些内存的浪费，比如当只需分配一个小对象时，为了这个小对象可能要申请一大块的内存池，但这个浪费还是值得的，况且这种情况在实际应用中也并不多见。 (2)**避免了内存碎片的生成**。程序中的小对象的分配极易造成内存碎片，给操作系统的内存管理带来了很大压力，系统中碎片的增多不但会影响内存分配的速度，而且会极大地降低内存的利用率。以内存池组织小对象的内存，从系统的角度看，只是一大块内存池，看不到小对象内存的分配和释放。

free-lists的节点结构如下：

union obj {
            union obj * free_list_link;
            char client_data[1];    /* The client sees this. */
      };

注意：

**为了维护链表，每个节点需要额外的指针指向下一个节点，这不就造成了额外负担吗？**

答：使得，但是注意上述obj所用的是union，由于union之故，从其第一个字段观之，obj可被视为一个指针，指向相同形式的另一个obj；从其第二字段观之，obj可被视为一个指针，指向实际区块。一物二用的结果是，不会为了维护链表所必须的指针而造成内存的另一种浪费。该技巧在强型语言如java中行不通，但在非强型语言如C++中很普遍。

![Center 1][]

// 以下是第二级配置器
    // 注意，无"template型别参数"，且第二参数完全没派上用场
    // 第一参数用于多线程环境
    template <bool threads, int inst>
    class __default_alloc_template {
    
    private:
      // Really we should use static const int x = N
      // instead of enum { x = N }, but few compilers accept the former.
    # ifndef __SUNPRO_CC
        enum {__ALIGN = 8};                          // 小型区块的上调边界
        enum {__MAX_BYTES = 128};                    // 小型区块的上限
        enum {__NFREELISTS = __MAX_BYTES/__ALIGN};   // free-lists 个数
    # endif
    
    // ROUND_UP()将 bytes 上调至 8 的倍数
    // 向上舍入操作  
    // 解释一下, __ALIGN - 1指明的是实际内存对齐的粒度  
    // 例如__ALIGN = 8时, 我们只需要7就可以实际表示8个数(0~7)  
    // 那么~(__ALIGN - 1)就是进行舍入的粒度  
    // 我们将(bytes) + __ALIGN-1)就是先进行进位, 然后截断  
    // 这就保证了我是向上舍入的  
    // 例如byte = 100, __ALIGN = 8的情况  
    // ~(__ALIGN - 1) = (1 000)B  
    // ((bytes) + __ALIGN-1) = (1 101 011)B  
    // (((bytes) + __ALIGN-1) & ~(__ALIGN - 1)) = (1 101 000 )B = (104)D  
    // 104 / 8 = 13, 这就实现了向上舍入  
    // 对于byte刚好满足内存对齐的情况下, 结果保持byte大小不变  
    // 记得《Hacker's Delight》上面有相关的计算  
    // 这个表达式与下面给出的等价  
    // ((((bytes) + _ALIGN - 1) * _ALIGN) / _ALIGN)  
    // 但是SGI STL使用的方法效率非常高  
     static size_t ROUND_UP(size_t bytes) {
            return (((bytes) + __ALIGN-1) & ~(__ALIGN - 1));
      }
    
    
    __PRIVATE:
    // 管理内存链表用   // 为了尽最大可能减少内存的使用, 这里使用一个union  
    // 如果使用第一个成员, 则指向另一个相同的union obj  
    // 而如果使用第二个成员, 则指向实际的内存区域  
    // 这样就实现了链表结点只使用一个指针的大小空间, 却能同时做索引和指向内存区域  
    // 这个技巧性非常强, 值得学习  
      union obj { // free-lists的节点构造
            union obj * free_list_link;
            char client_data[1];    /* The client sees this. */
      };
    private:
    # ifdef __SUNPRO_CC
        static obj * __VOLATILE free_list[]; 
            // Specifying a size results in duplicate def for 4.1
    # else
    	// 16个free-lists，对应的内存链容量为8、16、24、……、128
        static obj * __VOLATILE free_list[__NFREELISTS]; 
    # endif
    	// 以下函数根据区块大小，决定使用第 n 号free-list。n从0起算
    	static  size_t FREELIST_INDEX(size_t bytes) {
    		return (((bytes) + __ALIGN-1)/__ALIGN - 1);
    	}
    
    	// 返回一个大小为 n 的对象，并可能加入大小为 n 的其他区块到 free list
      	static void *refill(size_t n);
    	// 配置一大块空间，可容纳 nobjs 个大小为"size"的区块
    	// 如果配置 nobjs 个区块有所不便，nobjs可能会降低
    	static char *chunk_alloc(size_t size, int &nobjs);
    
      	// Chunk allocation state.
      	static char *start_free; // 内存池起始位置。只在 chunk_alloc() 中变化
      	static char *end_free;   // 内存池结束位置。只在 chunk_alloc() 中变化
      	static size_t heap_size; //已经在堆上分配的空间大小
    
    // 下面三个条件编译给多线程条件下使用锁提供必要支持
    # ifdef __STL_SGI_THREADS
        static volatile unsigned long __node_allocator_lock;
        static void __lock(volatile unsigned long *); 
        static inline void __unlock(volatile unsigned long *);
    # endif
    
    # ifdef __STL_PTHREADS
        static pthread_mutex_t __node_allocator_lock;
    # endif
    
    # ifdef __STL_WIN32THREADS
        static CRITICAL_SECTION __node_allocator_lock;
        static bool __node_allocator_lock_initialized;
    
      public:
        __default_alloc_template() {
    	// This assumes the first constructor is called before threads
    	// are started.
            if (!__node_allocator_lock_initialized) {
                InitializeCriticalSection(&__node_allocator_lock);
                __node_allocator_lock_initialized = true;
            }
        }
      private:
    # endif
    
        // 用于多线程环境下锁定操作
        class lock {
            public:
                lock() { __NODE_ALLOCATOR_LOCK; }
                ~lock() { __NODE_ALLOCATOR_UNLOCK; }
        };
        friend class lock;
    
    public:
      static void * allocate(size_t n);
      static void deallocate(void *p, size_t n);
      static void * reallocate(void *p, size_t old_sz, size_t new_sz);
    } ;
    
    // 以下是 static data member 的定义与初值设定
    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>
    __default_alloc_template<threads, inst>::obj * __VOLATILE
    __default_alloc_template<threads, inst> ::free_list[
    # ifdef __SUNPRO_CC
        __NFREELISTS
    # else
        __default_alloc_template<threads, inst>::__NFREELISTS
    # endif
    ] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };

#    空间配置函数 allocate() #

此函数首先判断区块大小，大于 128 bytes 就调用第一级配置器，小于 128 bytes 就检查对应的 free list。如果 free list 之内有可用的区块，就直接拿来用，如果没有可用区块，就将区块大小上调至 8 倍数边界，然后调用 refill()，准备为 free list 重新填充空间。

/* n must be > 0 */
    static void * allocate(size_t n)
    {
        obj * __VOLATILE * my_free_list;
        obj * __RESTRICT result;
    
        // 大于128 就调用第一级配置器
        if (n > (size_t) __MAX_BYTES) {
            return(malloc_alloc::allocate(n));
        }
        // 寻找 16 个free lists中适当的一个
        my_free_list = free_list + FREELIST_INDEX(n);
        // Acquire the lock here with a constructor call.
        // This ensures that it is released in exit or during stack
        // unwinding.
        #ifndef _NOTHREADS
        /*REFERENCED*/
        lock lock_instance;
        #endif
        result = *my_free_list;
        if (result == 0) {
            // 没找到可用的 free list，准备重新填充 free list
            void *r = refill(ROUND_UP(n));
            return r;
        }
        // 调整 free list
        *my_free_list = result -> free_list_link;
        return (result);
    };

![Center 2][]

# 空间释放函数deallocate() #

该函数首先判断区块大小，大于 128 bytes 就调用第一级配置器，小于 128 bytes 就找出对应的 free list，将区块回收。

/* p 不可以是 0 */
    static void deallocate(void *p, size_t n)
    {
    	obj *q = (obj *)p;
        	obj * __VOLATILE * my_free_list;
    
    	// 大于 128 就调用第一级配置器
        	 if (n > (size_t) __MAX_BYTES) {
                    malloc_alloc::deallocate(p, n);
            	return;
        	}
    
    	// 寻找对应的 free list
        	my_free_list = free_list + FREELIST_INDEX(n);
        	// acquire lock
            #ifndef _NOTHREADS
            /*REFERENCED*/
            lock lock_instance;
            #endif /* _NOTHREADS */
    
    	// 调整 free list，回收区块
        	q -> free_list_link = *my_free_list;
        	*my_free_list = q;
        	// lock is released here
    }

![Center 3][]

# 重新填充 free lists #

前面的 allocate()，当它发现 free list 中没有可用区块时，就调用 refille()，准备为 free list 重新填充空间。新的空间将取自内存池（经由 chunk\_alloc()完成）。缺省取得 20 个新节点（新区块），但万一内存池空间不足，获得的节点数（区块数）可能小于 20。

// 返回一个大小为 n 的对象，并且有时候会为适当的 free list 增加节点
    // 假设 n 已经适当上调至 8 的倍数
    /* We hold the allocation lock. */
    template <bool threads, int inst>
    void* __default_alloc_template<threads, inst>::refill(size_t n)
    {
        int nobjs = 20;
        // 调用 chunk_alloc()，尝试取得 nobjs 个区块作为 free list 的新节点
        // 注意参数 nobjs 是 pass by reference
        char * chunk = chunk_alloc(n, nobjs);
        obj * __VOLATILE * my_free_list;
        obj * result;
        obj * current_obj, * next_obj;
        int i;
    
        // 如果只获得一个区块，这个区块就分配给调用者用，free list无新节点
        if (1 == nobjs) return(chunk);
        // 否则准备调整 free list，纳入新节点
        my_free_list = free_list + FREELIST_INDEX(n);
    
        // 以下在 chunk 空间内建立 free list
        result = (obj *)chunk; // 这一块准备返回给客户端
    
        // 以下导引 free list 指向新配置的空间(取自内存池)
        *my_free_list = next_obj = (obj *)(chunk + n);
        // 以下将 free list的各节点串接起来
        for (i = 1; ; i++) { // 从 1 开始，因为第 0 个将返回给客端
            current_obj = next_obj;
            next_obj = (obj *)((char *)next_obj + n);
            if (nobjs - 1 == i) {
                current_obj -> free_list_link = 0;
                break;
            } else {
                current_obj -> free_list_link = next_obj;
            }
    	}
    
        return(result);
    }

# 内存池 #

从内存池中取空间给 free list使用，是chunk\_alloc()的工作：

// 假设 size 已经适当上调至 8 的倍数
    // 注意参数 nobjs 是 pass by reference
    template <bool threads, int inst>
    char*
    __default_alloc_template<threads, inst>::chunk_alloc(size_t size, int& 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 = size * nobjs;
            result = start_free;
            start_free += total_bytes;
            return(result);
        } else {
        	// 内存池剩余空间连一个区块的大小都无法提供
            size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
            // 以下试着让内存池中的残余零头还有利用价值(零头也应该是 8 的倍数)
            if (bytes_left > 0) {
    			// 内存池内还有一些零头，先配给适当的free list
    			// 首先寻找适当的 free list
                obj * __VOLATILE * my_free_list =
                            free_list + FREELIST_INDEX(bytes_left);
    
    			// 调整 free list，将内存池中的残余空间编入
                ((obj *)start_free) -> free_list_link = *my_free_list;
                *my_free_list = (obj *)start_free;
            }
    
    		// 配置 heap 空间，用来补充内存池
            start_free = (char *)malloc(bytes_to_get);
            if (0 == start_free) {
    			// heap空间不足，malloc()失败
                int i;
                obj * __VOLATILE * my_free_list, *p;
                // Try to make do with what we have.  That can't
                // hurt.  We do not try smaller requests, since that tends
                // to result in disaster on multi-process machines.
                // 试着检视我们手上拥有的东西。这不会造成伤害。我们不打算尝试配置
                // 较小的区块，因为那在多进程(multi-process)机器上容易导致灾难
                // 以下搜寻适当的 free list
                // 所谓适当是指"尚有未用区块，且区块够大"之 free list
                for (i = size; i <= __MAX_BYTES; i += __ALIGN) {
                    my_free_list = free_list + FREELIST_INDEX(i);
                    p = *my_free_list;
                    if (0 != p) { // free list内尚有未用区块
                    	// 调整free list以释出未用区块
                        *my_free_list = p -> free_list_link;
                        start_free = (char *)p;
                        end_free = start_free + i;
    		    // 递归调用自己，为了修正 nobjs
                        return(chunk_alloc(size, nobjs));
    		    // 注意，任何残余零头终将被编入适当的free-list中备用
                    }
                }
    
    	end_free = 0;	// 如果出现意外，到处都没内存可用
    	// 调用第一级配置器，看看 out-of-memory 机制能否尽点力
    	start_free = (char *)malloc_alloc::allocate(bytes_to_get);
            // 这会导致抛出异常(exception)，或内存不足的情况获得改善
            }
            heap_size += bytes_to_get;
            end_free = start_free + bytes_to_get;
    	// 递归调用自己，为了修正 nobjs
            return(chunk_alloc(size, nobjs));
        }
    }

上述的chunk\_alloc()函数以 end\_free - start\_free 来判断内存池的水量。如果水量充足，就直接调用 20 个区块返回给 free list。如果水量不足以提供 20 个区块，但还最后供应一个以上的区块，就拔出这不足 20 个区块的空间出去。这时候其 pass by reference的nobjs参数将被修改为实际能够供应的区块数。如果内存池连一个区块空间都无法供应，对客端显然无法交待，此时便需利用 malloc() 从head中配置内存，为内存池注入源头活水以应付需求。新水量的大小为需求量的两倍，再加上一个随着配置次数增加而愈来愈大的附加量。

[Center]: /images/20220805/f264c65e57db4d099108237c718ea12c.png
[Center 1]: /images/20220805/042028fbf54546b8b9274517d2e9add3.png
[Center 2]: /images/20220805/40d8154408e14c52b14e38eee9d7c0d9.png
[Center 3]: /images/20220805/376f3a35601f43919f1d8f01fcab5d84.png