STL源码分析：SGI STL的内存管理 allocator

超、凢脫俗 2023-05-30 06:06 89阅读 0赞

# 前言 #

STL源码的框架类精髓在于，它把对象的创建过程细分为两步，一步是申请内存，另外一步是在申请到的内存上调用构造函数初始化那一块内存。

今天来分析一个STL的alloc的源码，STL这么精妙的东西当然是会自己管理内存的啦~~·  
整体看下来，STL的内存管理比操作系统内存管理的简单太多了。。。

# 整体轮廓 #

STL源码里面，有两个allocator,一个被称为\_\_malloc\_alloc\_template,另外一个被称为\_\_default\_alloc\_template。  
\_\_malloc\_alloc\_template被称为一级内存分配管理器，其主要需要是通过malloc和free来管理内存的。  
\_\_default\_alloc\_template被称为二级内存分配管理器，主要是拥有一个内存池，通过alloc函数向系统申请内存某些指定大小的内存块，然后把内存块放到自己的内存池里面管理。二级内存分配管理器主要管理的是小内存的块，对于大内存的块还是通过malloc来管理的。

SGI版本的STL通过`__USE_MALLOC` 宏来定义是 只使用一级内存管理器，还是两个都使用。默认是两个都使用。

# ifdef __USE_MALLOC
    
    typedef malloc_alloc alloc;
    typedef malloc_alloc single_client_alloc;
    
    # else
    ···
    typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;
    typedef __default_alloc_template<false, 0> single_client_alloc;
    ···

两个内存管理器都要实现如下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)); }
    };

# 一级内存分配器 #

一级内存分配器就是基于malloc的，这一级的就很简单，基本上都是对c的malloc,realloc,free进行了一次封装，再加上内存不足的处理。

主要的成员函数：

## 内存分配：static void \* allocate(size\_t n) ##

static void * allocate(size_t n)
    { 
        void *result = malloc(n);
        if (0 == result) result = oom_malloc(n);
        return result;
    }

逻辑是先使用malloc申请n个字节的内存，如果分配失败，调用oom\_malloc函数。这个函数用于处理out\_of\_memory情况下的内存分配。  
其实现为：逻辑是一个for循环，for循环调用out of memory的处理函数\_\_malloc\_alloc\_oom\_handler,然后不断的尝试malloc新的内存，直到成功。

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

其中`__malloc_alloc_oom_handler;`的默认值为0，说明没内存的时候就直接抛出异常了。

#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
    template <int inst>
    void (* __malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = 0;
    #endif

当然，可以通过函数`set_malloc_handler` 来设置。

## 回收内存：static void deallocate(void *p, size\_t /* n \*/) ##

直接就是free了，简单粗暴。

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

## 重新分配：reallocte ##

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

其中realloc是C的函数，其功能按以下二者之一执行：

a) 可能的话，扩张或收缩 ptr 所指向的已存在内存。内容在新旧大小中的较小者范围内保持不变。若扩张范围，则数组新增部分的内容是未定义的。  
b) 分配一个大小为 new\_size 字节的新内存块，并复制大小等于新旧大小中较小者的内存区域，然后释放旧内存块。  
若无足够内存，则不释放旧内存块，并返回空指针。

# 二级内存管理器：\_\_default\_alloc\_template #

这个是SGI STL使用的默认内存管理器，它拥有自己的内存池，这些内存块都是用于应对小内存申请需求的。  
首先通过枚举，定义三个常量：\_\_ALIGN，\_\_MAX\_BYTES和\_NFREELISTS。

#ifdef __SUNPRO_CC
    // breaks if we make these template class members:
      enum { __ALIGN = 8};//对齐的baseline，所有的块的大小都是它的倍数。
      enum { __MAX_BYTES = 128};//最大的区块
      enum { __NFREELISTS = __MAX_BYTES/__ALIGN};//链表的条数
    #endif

## 成员变量 ##

static obj * __VOLATILE free_list[__NFREELISTS]; 
    static char *start_free;
    static char *end_free;
    static size_t heap_size;

二级内存管理器，通过一个链表的线性表来维护所有的空闲块。  
free\_list是一个`obj*`的指针数组，obj是一个union，它的定义为

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

一个obj至少需要4个字节的内存，因为它的两个成员都是指针。当它所在的内存是空闲的时候就使用free\_list\_link成员，而当它是分配出去后就使用client\_data字段。

整个free\_list的逻辑结构就类似于下图，数组的元素指定一个空闲的链表。每个空闲的链表都是由相同大小的空闲的块链接起来的。比如free\_list\[0\]指向的就是各个块大小为1x\_\_ALIGN的空闲链表，而free\_list\[1\]指向大小全部为2x\_\_ALIGN的块串起来的链表。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ptaDE5OTY_size_16_color_FFFFFF_t_70]  
start\_free和end\_free 用于维护当前内存池的起始地址和终止地址。

为啥既有free\_list还要内存池呢？其实他们的关系是这样的：  
alloc一开始不带有任何的内存资源，那么首先alloc会使用malloc申请一大波内存，这一大波内存有一部分直接划给了当前的请求，剩下一部分挂到了free\_list里面特定的元素所指向的链表上，最后还会剩下一部分就划到自己的内存池里面，并用start\_free和end\_free维护这剩余的内存池里面那些已经使用了，那些没有使用。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ptaDE5OTY_size_16_color_FFFFFF_t_70 1]

## 成员函数 ##

### `ROUND_UP(size_t bytes)` ###

这个函数用于把bytes向上取整到离\_\_ALIGN最近的正整数减一。

static size_t ROUND_UP(size_t bytes) { 
            return (((bytes) + __ALIGN-1) & ~(__ALIGN - 1));//先+7,然后最后3位填充0
      }

注意，bytes需要大于0。而且有ROUND\_UP(8)等于8。ROUND\_UP(9)=16。

### `FREELIST_INDEX(size_t bytes)` ###

求bytes应该挂在free\_list的那一个元素指向的链表上。

static  size_t FREELIST_INDEX(size_t bytes) { 
            return (((bytes) + __ALIGN-1)/__ALIGN - 1);
      }

一样的结果为bytes向上取整为\_\_ALIGN最小倍数减一。

例如：  
FREELIST\_INDEX(8)=0,FREELIST\_INDEX(9)=1。

### `allocate(size_t n)` ###

内存分配函数，n是请求的字节数。

/* n must be > 0 */
      static void * allocate(size_t n)
      { 
        obj * __VOLATILE * my_free_list;
        obj * __RESTRICT result;
    
        if (n > (size_t) __MAX_BYTES) { 
            return(malloc_alloc::allocate(n));
        }
        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) { 
            void *r = refill(ROUND_UP(n));
            return r;
        }
        *my_free_list = result -> free_list_link;
        return (result);
      };

逻辑是：  
1.首先判断n是否大于\_\_MAX\_BYTES也就是128，如果大于直接走malloc\_alloc::allocate(n)函数，而这个函数本质就是调用malloc()。这么做表示这次请求的是一大块内存，无需STL去维护它。为啥会觉得128字节是个很大的块呢？这是因为这个代码时1993年写的，对于当时来说，128字节是很大的了。

2.如果n不大于128，则说明这是小碎片，可能这种小碎片会在后期频繁的申请。而这种小碎片申请一次就要调用malloc，这是得不偿失的，因为malloc本身是个很耗时的操作。

**为啥要自己去维护这种小碎片的内存块呢？** 主要是考虑到，这种小碎片频繁的malloc会很耗时，而且根据局部性原理，小碎片被重复利用的可能性会比较高。总而言之，自己维护小碎片是为了提高内存管理的时间效率。  
3.

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;

这两句话等价于：`result=free_list[FREELIST_INDEX(n)]`，也就是取n在数组上下标。  
4.

if (result == 0) { 
        void *r = refill(ROUND_UP(n));
        return r;
    }
    *my_free_list = result -> free_list_link;
    return (result);

先看看这个数组上的元素是不是0，如果是0，说明这种大小的空闲块目前没有了。于是要走refill去处理。refill需要做两件事：A.返回一个所求大小的内存块给用户 B.多申请几个这种大小的块，并把这些新申请的未使用的块初始化到free\_list上面去。

如果result不是0,说明当前就有一个符合条件的空闲块，于是把它从链表的表头摘下来，同时更新这个链表的表头为`result->free_list_link;`

### refill(size\_t n) ###

从allocate(size\_t n) 函数可以知道，当free\_list\[FREELIST(n)\]上没有空闲块的时候，就会调用这个refill函数。那么猜也能猜到，refill无外乎两件事，最重要的是从内存池里面拿一块大小为ROUND\_UP(n)的内存下来先满足当前的请求，其次如果有多余的内存就再顺带着在free\_list\[FREELIST(n)\]链表上多挂几个空闲的块上去，方便下回来取这种大小的块。

template <bool threads, int inst>
    void* __default_alloc_template<threads, inst>::refill(size_t n)
    { 
        int nobjs = 20;
        char * chunk = chunk_alloc(n, nobjs);
        obj * __VOLATILE * my_free_list;
        obj * result;
        obj * current_obj, * next_obj;
        int i;
    
        if (1 == nobjs) return(chunk);
        my_free_list = free_list + FREELIST_INDEX(n);
    
        /* Build free list in chunk */
          result = (obj *)chunk;
          *my_free_list = next_obj = (obj *)(chunk + n);
          for (i = 1; ; i++) { 
            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);
    }

首先，refill就狮子大开口，先通过chunk\_alloc(n,nobjs)申请20个大小为n的连续内存块。注意这里的n已经被上层调用者向上取整到8的倍数了。`chunk_alloc(size_t size, int& nobjs)`函数就会根据自己的能力，尽力而为地满足它的请求。什么叫尽量呢？看后面的chunk\_alloc我们晓得，chunk\_alloc会看看当前内存池的剩余量end\_free-start\_free是否够，能给多少给多少。并通过nobjs告诉refill它给了几个chunk。这个nobjs是个引用，即是参数又是结果。

refill拿着从chunk\_alloc返回的块，先看看chunk\_alloc到底返回了几个chunk。  
如果发现`nobjs`就是1，那么refill当然就只能把这仅有的一个chunk返回给申请者咯。  
如果发现`nobjs`大于1，说明chunk\_alloc比较给力，一次性给了很多个。  
于是呢，它就把剩下的nobjs-1个chunk全部用`objs*`链表链接起来。

### chunk\_alloc函数 ###

这个函数是很有意思滴。

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);
            // Try to make use of the left-over piece.
            if (bytes_left > 0) { 
                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) { 
                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.
                for (i = size; i <= __MAX_BYTES; 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));
                        // Any leftover piece will eventually make it to the
                        // right free list.
                    }
                }
    	    end_free = 0;	// In case of exception.
                start_free = (char *)malloc_alloc::allocate(bytes_to_get);
                // This should either throw an
                // exception or remedy the situation. Thus we assume it
                // succeeded.
            }
            heap_size += bytes_to_get;
            end_free = start_free + bytes_to_get;
            return(chunk_alloc(size, nobjs));
        }
    }

这个函数的逻辑在于：

1.  首先计算nobjs个size总共需要多少多少内存空间total\_bytes，一般来说nobjs=20,size是8的倍数。
2.  同时计算当前内存池，剩余多少：bytes\_left= end\_free- start\_free
3.  如果发现，供大于求，那么直接从内存池划分出total\_bytes内存即可
4.  如果发现，供只能满足部分的请求，那么就只把自己能够支持的最大的内存返回去，同时修改nobjs为bytes\_left/size.
5.  如果发现内存池一个size都不满足，那需要申请新的内存池了，同时内存池可能还留着一些零头，把这些零头挂在相应的free\_list上。
    
    5.1 首先判断bytes\_left是否大于0，如果大于0；说明内存池有剩余，只不过小于size而已。内存这么金贵，肯定不能浪费。于是就把这个bytes\_left零头的内存之间挂到free\_list\[FREELIST\_INDEX(bytes\_left)\]上。比如说bytes\_left=8,而size=128,那么这多出来的8字节的内存池零头就被挂在free\_list\[0\]这个链表上。  
    值得注意的是bytes\_left一定是\_\_ALIGN的倍数，一定不会出现bytes\_left不能刚好吻合上free\_list\[FREELIST\_INDEX(bytes\_left)\]所需大小的情况。这是因为内存池在申请的时候，申请初始大小为\_\_ALIGN的倍数，而每次分配出现的大小也是\_\_ALIGN的倍数，那么剩下的肯定只能是0或\_\_ALIGN的倍数。  
    5.2 处理完零头，就重新去申请新的内存，申请的大小为2x total\_size+ROUND\_UP(heap\_size>>4);新申请2倍的请求加上原来内存池总大小的1/16向上取8的倍数整。可以看出，一次申请就会申请超出当前需求的，为以后的申请做准备。  
    5.3 如果申请内存成功的话，就把内存池需要的end\_free变量更新一下，然后再调用一次chunk\_allocate。  
    5.4 如果发现连malloc都申请失败的话，说明当前整个操作系统的内存都不足了。这个时候，  
    执行0==start\_free的分支

if (0 == start_free) { 
                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.
                for (i = size; i <= __MAX_BYTES; 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));
                        // Any leftover piece will eventually make it to the
                        // right free list.
                    }
                }
    	    end_free = 0;	// In case of exception.
                start_free = (char *)malloc_alloc::allocate(bytes_to_get);
                // This should either throw an
                // exception or remedy the situation. Thus we assume it
                // succeeded.
            }

首先是个for循环，for里面让i从一个size开始往\_MAX\_BYTES找，如果i这个大小的free\_list上的那个链表刚好是有空闲的，那么就把这个链表的表头的那个块摘下来，丢回给内存池里面去。这里的丢回内存池，通过`start_free=p;end_free=start_free+i` 来实现。然后再重新调用chunk\_alloc。在下一次chunk\_alloc的时候，就会走`bytes_left >= size` 或`bytes_left >= total_bytes`的逻辑，因为内存池此时是回收到了至少容纳一个size的内存。

如果for循环跑完后，没有找到任何的足够大的可以回收到内存池的chunk,那么此时就把申请内存交给一级内存管理器的allocate，这个allocate的逻辑是，先调用malloc，如果分配失败则调用异常处理函数。

### deallocate(void \*p,size\_t n) ###

/* p may not be 0 */
      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;
        }
        my_free_list = free_list + FREELIST_INDEX(n);
        // acquire lock
    # ifndef _NOTHREADS
            /*REFERENCED*/
            lock lock_instance;
    # endif /* _NOTHREADS */
        q -> free_list_link = *my_free_list;
        *my_free_list = q;
        // lock is released here
      }

这个函数用于释放位置在p,大小为n的内存。函数的逻辑是把这个块挂到free\_list的某个链表上面去。

### reallocate(void \*p, size\_t old\_sz,size\_t new\_sz) ###

这个函数用于在指针p处再 reallocate一个新的大小。

template <bool threads, int inst>
    void*
    __default_alloc_template<threads, inst>::reallocate(void *p,
                                                        size_t old_sz,
                                                        size_t new_sz)
    { 
        void * result;
        size_t copy_sz;
    
        if (old_sz > (size_t) __MAX_BYTES && new_sz > (size_t) __MAX_BYTES) { 
            return(realloc(p, new_sz));
        }
        if (ROUND_UP(old_sz) == ROUND_UP(new_sz)) return(p);
        result = allocate(new_sz);
        copy_sz = new_sz > old_sz? old_sz : new_sz;
        memcpy(result, p, copy_sz);
        deallocate(p, old_sz);
        return(result);
    }

其逻辑在于，首先看old\_sz和new\_sz是不是都超出128，都大于128说明这个是个大块。那么就把这个问题交给标注库函数realloc处理。  
如果向上取值后old\_sz和new\_sz都是相同的8的倍数，那么就直接返回指针p。  
否则，使用这个类的allocate函数，申请new\_sz个字节的内存。再把p开头的copy\_sz个字节拷贝到新申请的内存块。其中new\_sz取new\_sz和old\_sz的最小值。  
最后再释放原来的内存块。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ptaDE5OTY_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191107191259209.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ptaDE5OTY=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ptaDE5OTY_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191107192842509.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ptaDE5OTY=,size_16,color_FFFFFF,t_70