STL源代码剖析-05 stl_alloc.h(2)

在STL源代码剖析-04 stl_alloc.h(1) 中讲了大额内存(大于128byte)是怎么分配的现在主要来看≤128bytes是怎么做的。先看三个枚举常量：

enum {_ALIGN = 8};
  enum {_MAX_BYTES = 128};
  enum {_NFREELISTS = 16}; // _MAX_BYTES/_ALIGN

分配小内存是通过己申请的内存进行分配的，它通过16(_NFREELISTS)个链表来管理申请的内存。而且分配的倍数是8(_ALIGN)的倍数，就算你申请1byte它也会给你分配8byte。16*8=128(_MAX_BYTES)。所以可以看到这16个链表节点分别是大小为8，16，24，... ... ，128bytes.

union _Obj {
        union _Obj* _M_free_list_link;
        char _M_client_data[1];    /* The client sees this.        */
  };

这就是链表结构了，可以看到它是union类型，这主要是为了结省空间，即当空间不被使用时就是指针，否则就是存储数据。再看它的数据成员：

template <bool __threads, int __inst>
char* __default_alloc_template<__threads, __inst>::_S_start_free = 0;

template <bool __threads, int __inst>
char* __default_alloc_template<__threads, __inst>::_S_end_free = 0;

template <bool __threads, int __inst>
size_t __default_alloc_template<__threads, __inst>::_S_heap_size = 0;

template <bool __threads, int __inst>
typename __default_alloc_template<__threads, __inst>::_Obj* __STL_VOLATILE
__default_alloc_template<__threads, __inst> ::_S_free_list[
# if defined(__SUNPRO_CC) || defined(__GNUC__) || defined(__HP_aCC)
    _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, };

可以看到初始值都是10，并且链表数据的指针都是NULL，现在就来看看主要部分，分配内存和重新分配内存是怎么做的：

/* __n must be > 0      */
  static void* allocate(size_t __n)
  {
    void* __ret = 0;

    if (__n > (size_t) _MAX_BYTES) {
      __ret = malloc_alloc::allocate(__n);
    }
    else {
      _Obj* __STL_VOLATILE* __my_free_list
          = _S_free_list + _S_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
      _Obj* __RESTRICT __result = *__my_free_list;
      if (__result == 0)
        __ret = _S_refill(_S_round_up(__n));
      else {
        *__my_free_list = __result -> _M_free_list_link;
        __ret = __result;
      }
    }

    return __ret;
  };

首先它看要分配的大小__n，如果大于_MAX_BYTES就使用malloc_alloc来分配，就是上一节讲的那个内存分配类

typedef __malloc_alloc_template<0> malloc_alloc;

 如果不是，先找到那个链表的下标：

static  size_t _S_freelist_index(size_t __bytes) {
        return (((__bytes) + (size_t)_ALIGN-1)/(size_t)_ALIGN - 1);
  }

因为下标是0开始的，所以最后还要-1。如要分配是22byte，因为实际应该分配24（3*8）byte，它的链表下标是2（0-8，1-16，2-24），所以先是（22+7）/ 8 - 1=2. my_free_list 就是那个地方了，如果它不为0，就是这个链表不为空，则将最前面结点（不一定是一个结点，应该是一块内存，大小为24byte）分配出来作为分配的内存，并删除这个结点（一块内存，即从链表中删除它），如果不够，就调用_S_refill(_S_round_up(__n))来分配。_S_round_up(__n)是把__n作为最接近__n的8的倍数。

static size_t
  _S_round_up(size_t __bytes)
    { return (((__bytes) + (size_t) _ALIGN-1) & ~((size_t) _ALIGN - 1)); }

很巧妙的办法，先将__bytes变成一个最接近的8的倍数还大一点，但不会大于7的数，再将低位的二进制1变为0，就是最接近的8的倍数了。看看_S_refill是怎么做的：由于它最优调用了_S_chunk_alloc，先看这个函数：

/* We allocate memory in large chunks in order to avoid fragmenting     */
/* the malloc heap too much.                                            */
/* We assume that size is properly aligned.                             */
/* We hold the allocation lock.                                         */
template <bool __threads, int __inst>
char*
__default_alloc_template<__threads, __inst>::_S_chunk_alloc(size_t __size,
                                                            int& __nobjs)
{
    char* __result;
    size_t __total_bytes = __size * __nobjs;
    size_t __bytes_left = _S_end_free - _S_start_free;

    if (__bytes_left >= __total_bytes) {
        __result = _S_start_free;
        _S_start_free += __total_bytes;
        return(__result);
    } else if (__bytes_left >= __size) {
        __nobjs = (int)(__bytes_left/__size);
        __total_bytes = __size * __nobjs;
        __result = _S_start_free;
        _S_start_free += __total_bytes;
        return(__result);
    } else {
        size_t __bytes_to_get =  2 * __total_bytes + _S_round_up(_S_heap_size >> 4);
        // Try to make use of the left-over piece.
        if (__bytes_left > 0) {
            _Obj* __STL_VOLATILE* __my_free_list = _S_free_list + _S_freelist_index(__bytes_left);

            ((_Obj*)_S_start_free) -> _M_free_list_link = *__my_free_list;
            *__my_free_list = (_Obj*)_S_start_free;
        }
        _S_start_free = (char*)malloc(__bytes_to_get);
        if (0 == _S_start_free) {
            size_t __i;
            _Obj* __STL_VOLATILE* __my_free_list;
        _Obj* __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 <= (size_t) _MAX_BYTES;
                 __i += (size_t) _ALIGN) {
                __my_free_list = _S_free_list + _S_freelist_index(__i);
                __p = *__my_free_list;
                if (0 != __p) {
                    *__my_free_list = __p -> _M_free_list_link;
                    _S_start_free = (char*)__p;
                    _S_end_free = _S_start_free + __i;
                    return(_S_chunk_alloc(__size, __nobjs));
                    // Any leftover piece will eventually make it to the
                    // right free list.
                }
            }
        _S_end_free = 0;    // In case of exception.
            _S_start_free = (char*)malloc_alloc::allocate(__bytes_to_get);
            // This should either throw an
            // exception or remedy the situation.  Thus we assume it
            // succeeded.
        }
        _S_heap_size += __bytes_to_get;
        _S_end_free = _S_start_free + __bytes_to_get;
        return(_S_chunk_alloc(__size, __nobjs));
    }
}

前两个if还是很好理解的，一个是尝试分配__nobjs个__size个，能分配出去就分配，如果不足就先看最少能分配多少个__size分配出去。因为__nobjs是个值-结果参数，所以我们能知道最后分配了多少个__size.如果不足__size，尝试申请__bytes_to_get byte的内存。先将剩下的不足__size的那些内存挂到相应大小的链表里（肯定<128 bytes），然后尝试申请内存，如果申请失败就在大于等于__size的那些链表里面找看看是不是有，如果有，那么这一块就拿出来用。如果这也没有，再尝试用 

_S_start_free = (char*)malloc_alloc::allocate(__bytes_to_get);

分配内存，由上一节我们知道如果它失败，则会退出程序或抛出异常。如果成功，则再分配。

template <bool __threads, int __inst>
void*
__default_alloc_template<__threads, __inst>::_S_refill(size_t __n)
{
    int __nobjs = 20;
    char* __chunk = _S_chunk_alloc(__n, __nobjs);
    _Obj* __STL_VOLATILE* __my_free_list;
    _Obj* __result;
    _Obj* __current_obj;
    _Obj* __next_obj;
    int __i;

    if (1 == __nobjs) return(__chunk);
    __my_free_list = _S_free_list + _S_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 -> _M_free_list_link = 0;
            break;
        } else {
            __current_obj -> _M_free_list_link = __next_obj;
        }
      }
    return(__result);
}

好了，如果上一次函数没有抛出异常，那么就谢天谢地了，终于有内存了，根据nobjs的值我们可以知道分配了多少倍我们需要的大小，如果为1，那么就没办剩余了，全得用掉，否则我们把多余的内存切成一块块大小为__n的块，挂到相应的链表中，以便下次需要。看看23行

__current_obj -> _M_free_list_link = 0;

因为它知道上一次连表为空的情况下才调用的函数，所以它直接把最后一块指针置为NULL。

/* __p may not be 0 */
  static void deallocate(void* __p, size_t __n)
  {
    if (__n > (size_t) _MAX_BYTES)
      malloc_alloc::deallocate(__p, __n);
    else {
      _Obj* __STL_VOLATILE*  __my_free_list
          = _S_free_list + _S_freelist_index(__n);
      _Obj* __q = (_Obj*)__p;

      // acquire lock
#       ifndef _NOTHREADS
      /*REFERENCED*/
      _Lock __lock_instance;
#       endif /* _NOTHREADS */
      __q -> _M_free_list_link = *__my_free_list;
      *__my_free_list = __q;
      // lock is released here
    }
  }

释放内存就比较简单了，如果是小块的，那么直接放到相应链表中，如果是>128bytes时，用free释放掉。有了allocate的基础，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 (_S_round_up(__old_sz) == _S_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);
}

先判断用哪个类分配，再看看如果需要的内存是一样的，那么就不用变了，否则分配新内存。再根据分配的大小来决定拷贝多少数据放到新内存中，并deallocate掉老的内存。