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

2481阅读　0评论2012-04-11　_Rayx
分类：C/C++

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

  1. enum {_ALIGN = 8};
  2.   enum {_MAX_BYTES = 128};
  3.   enum {_NFREELISTS = 16}; // _MAX_BYTES/_ALIGN

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

  1. union _Obj {
  2.         union _Obj* _M_free_list_link;
  3.         char _M_client_data[1]; /* The client sees this. */
  4.   };
这就是链表结构了，可以看到它是union类型，这主要是为了结省空间，即当空间不被使用时就是指针，否则就是存储数据。再看它的数据成员：

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

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

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

  10. template <bool __threads, int __inst>
  11. typename __default_alloc_template<__threads, __inst>::_Obj* __STL_VOLATILE
  12. __default_alloc_template<__threads, __inst> ::_S_free_list[
  13. # if defined(__SUNPRO_CC) || defined(__GNUC__) || defined(__HP_aCC)
  14.     _NFREELISTS
  15. # else
  16.     __default_alloc_template<__threads, __inst>::_NFREELISTS
  17. # endif
  18. ] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };
可以看到初始值都是10，并且链表数据的指针都是NULL，现在就来看看主要部分，分配内存和重新分配内存是怎么做的：

  1. /* __n must be > 0 */
  2.   static void* allocate(size_t __n)
  3.   {
  4.     void* __ret = 0;

  6.     if (__n > (size_t) _MAX_BYTES) {
  7.       __ret = malloc_alloc::allocate(__n);
  8.     }
  9.     else {
  10.       _Obj* __STL_VOLATILE* __my_free_list
  11.           = _S_free_list + _S_freelist_index(__n);
  12.       // Acquire the lock here with a constructor call.
  13.       // This ensures that it is released in exit or during stack
  14.       // unwinding.
  15. # ifndef _NOTHREADS
  16.       /*REFERENCED*/
  17.       _Lock __lock_instance;
  18. # endif
  19.       _Obj* __RESTRICT __result = *__my_free_list;
  20.       if (__result == 0)
  21.         __ret = _S_refill(_S_round_up(__n));
  22.       else {
  23.         *__my_free_list = __result -> _M_free_list_link;
  24.         __ret = __result;
  25.       }
  26.     }

  28.     return __ret;
  29.   };
首先它看要分配的大小__n，如果大于_MAX_BYTES就使用malloc_alloc来分配，就是上一节讲的那个内存分配类
  1. typedef __malloc_alloc_template<0> malloc_alloc;
 如果不是，先找到那个链表的下标：
  1. static size_t _S_freelist_index(size_t __bytes) {
  2.         return (((__bytes) + (size_t)_ALIGN-1)/(size_t)_ALIGN - 1);
  3.   }
因为下标是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的倍数。

  1. static size_t
  2.   _S_round_up(size_t __bytes)
  3.     { return (((__bytes) + (size_t) _ALIGN-1) & ~((size_t) _ALIGN - 1)); }
很巧妙的办法，先将__bytes变成一个最接近的8的倍数还大一点，但不会大于7的数，再将低位的二进制1变为0，就是最接近的8的倍数了。看看_S_refill是怎么做的：由于它最优调用了_S_chunk_alloc，先看这个函数：

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

  14.     if (__bytes_left >= __total_bytes) {
  15.         __result = _S_start_free;
  16.         _S_start_free += __total_bytes;
  17.         return(__result);
  18.     } else if (__bytes_left >= __size) {
  19.         __nobjs = (int)(__bytes_left/__size);
  20.         __total_bytes = __size * __nobjs;
  21.         __result = _S_start_free;
  22.         _S_start_free += __total_bytes;
  23.         return(__result);
  24.     } else {
  25.         size_t __bytes_to_get =  2 * __total_bytes + _S_round_up(_S_heap_size >> 4);
  26.         // Try to make use of the left-over piece.
  27.         if (__bytes_left > 0) {
  28.             _Obj* __STL_VOLATILE* __my_free_list = _S_free_list + _S_freelist_index(__bytes_left);

  30.             ((_Obj*)_S_start_free) -> _M_free_list_link = *__my_free_list;
  31.             *__my_free_list = (_Obj*)_S_start_free;
  32.         }
  33.         _S_start_free = (char*)malloc(__bytes_to_get);
  34.         if (0 == _S_start_free) {
  35.             size_t __i;
  36.             _Obj* __STL_VOLATILE* __my_free_list;
  37.      _Obj* __p;
  38.             // Try to make do with what we have. That can't
  39.             // hurt. We do not try smaller requests, since that tends
  40.             // to result in disaster on multi-process machines.
  41.             for (__i = __size;
  42.                  __i <= (size_t) _MAX_BYTES;
  43.                  __i += (size_t) _ALIGN) {
  44.                 __my_free_list = _S_free_list + _S_freelist_index(__i);
  45.                 __p = *__my_free_list;
  46.                 if (0 != __p) {
  47.                     *__my_free_list = __p -> _M_free_list_link;
  48.                     _S_start_free = (char*)__p;
  49.                     _S_end_free = _S_start_free + __i;
  50.                     return(_S_chunk_alloc(__size, __nobjs));
  51.                     // Any leftover piece will eventually make it to the
  52.                     // right free list.
  53.                 }
  54.             }
  55.      _S_end_free = 0;    // In case of exception.
  56.             _S_start_free = (char*)malloc_alloc::allocate(__bytes_to_get);
  57.             // This should either throw an
  58.             // exception or remedy the situation. Thus we assume it
  59.             // succeeded.
  60.         }
  61.         _S_heap_size += __bytes_to_get;
  62.         _S_end_free = _S_start_free + __bytes_to_get;
  63.         return(_S_chunk_alloc(__size, __nobjs));
  64.     }
  65. }
前两个if还是很好理解的，一个是尝试分配__nobjs个__size个，能分配出去就分配，如果不足就先看最少能分配多少个__size分配出去。因为__nobjs是个值-结果参数，所以我们能知道最后分配了多少个__size.如果不足__size，尝试申请__bytes_to_get byte的内存。先将剩下的不足__size的那些内存挂到相应大小的链表里（肯定<128 bytes），然后尝试申请内存，如果申请失败就在大于等于__size的那些链表里面找看看是不是有，如果有，那么这一块就拿出来用。如果这也没有，再尝试用 

  1. _S_start_free = (char*)malloc_alloc::allocate(__bytes_to_get);
分配内存，由上一节我们知道如果它失败，则会退出程序或抛出异常。如果成功，则再分配。

  1. template <bool __threads, int __inst>
  2. void*
  3. __default_alloc_template<__threads, __inst>::_S_refill(size_t __n)
  4. {
  5.     int __nobjs = 20;
  6.     char* __chunk = _S_chunk_alloc(__n, __nobjs);
  7.     _Obj* __STL_VOLATILE* __my_free_list;
  8.     _Obj* __result;
  9.     _Obj* __current_obj;
  10.     _Obj* __next_obj;
  11.     int __i;

  13.     if (1 == __nobjs) return(__chunk);
  14.     __my_free_list = _S_free_list + _S_freelist_index(__n);

  16.     /* Build free list in chunk */
  17.       __result = (_Obj*)__chunk;
  18.       *__my_free_list = __next_obj = (_Obj*)(__chunk + __n);
  19.       for (__i = 1; ; __i++) {
  20.         __current_obj = __next_obj;
  21.         __next_obj = (_Obj*)((char*)__next_obj + __n);
  22.         if (__nobjs - 1 == __i) {
  23.             __current_obj -> _M_free_list_link = 0;
  24.             break;
  25.         } else {
  26.             __current_obj -> _M_free_list_link = __next_obj;
  27.         }
  28.       }
  29.     return(__result);
  30. }
好了，如果上一次函数没有抛出异常，那么就谢天谢地了，终于有内存了，根据nobjs的值我们可以知道分配了多少倍我们需要的大小，如果为1，那么就没办剩余了，全得用掉，否则我们把多余的内存切成一块块大小为__n的块，挂到相应的链表中，以便下次需要。看看23行
  1. __current_obj -> _M_free_list_link = 0;
因为它知道上一次连表为空的情况下才调用的函数，所以它直接把最后一块指针置为NULL。

  1. /* __p may not be 0 */
  2.   static void deallocate(void* __p, size_t __n)
  3.   {
  4.     if (__n > (size_t) _MAX_BYTES)
  5.       malloc_alloc::deallocate(__p, __n);
  6.     else {
  7.       _Obj* __STL_VOLATILE* __my_free_list
  8.           = _S_free_list + _S_freelist_index(__n);
  9.       _Obj* __q = (_Obj*)__p;

  11.       // acquire lock
  12. # ifndef _NOTHREADS
  13.       /*REFERENCED*/
  14.       _Lock __lock_instance;
  15. # endif /* _NOTHREADS */
  16.       __q -> _M_free_list_link = *__my_free_list;
  17.       *__my_free_list = __q;
  18.       // lock is released here
  19.     }
  20.   }
释放内存就比较简单了，如果是小块的，那么直接放到相应链表中，如果是>128bytes时，用free释放掉。有了allocate的基础，reallocate也就比较简单了：

  1. template <bool threads, int inst>
  2. void*
  3. __default_alloc_template<threads, inst>::reallocate(void* __p,
  4.                                                     size_t __old_sz,
  5.                                                     size_t __new_sz)
  6. {
  7.     void* __result;
  8.     size_t __copy_sz;

  10.     if (__old_sz > (size_t) _MAX_BYTES && __new_sz > (size_t) _MAX_BYTES) {
  11.         return(realloc(__p, __new_sz));
  12.     }
  13.     if (_S_round_up(__old_sz) == _S_round_up(__new_sz)) return(__p);
  14.     __result = allocate(__new_sz);
  15.     __copy_sz = __new_sz > __old_sz? __old_sz : __new_sz;
  16.     memcpy(__result, __p, __copy_sz);
  17.     deallocate(__p, __old_sz);
  18.     return(__result);
  19. }
先判断用哪个类分配，再看看如果需要的内存是一样的，那么就不用变了，否则分配新内存。再根据分配的大小来决定拷贝多少数据放到新内存中，并deallocate掉老的内存。





上一篇：STL源代码剖析-04 stl_alloc.h(1)
下一篇：STL源代码剖析-06 stl_uninitialized.h