V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
codeboy18
V2EX  ›  C++

STL 源码分析--内存分配

  •  
  •   codeboy18 · 2021-02-24 19:45:09 +08:00 · 2107 次点击
    这是一个创建于 1129 天前的主题,其中的信息可能已经有所发展或是发生改变。

    更多精彩内容,请关注微信公众号:后端技术小屋

    说明:STL 采用 SGI 版本, 下载地址

    1 相关头文件

    stl_alloc.h
    alloc.h
    

    2 allocator

    STL 中默认使用的内存分配器,被广泛用于vector, hashmap, deque等数据结构中 该类实现以下接口:

    • allocate:给 n 个对象分配连续内存
    _Tp* allocate(size_type __n, const void* = 0) {
        return __n != 0 ? static_cast<_Tp*>(_Alloc::allocate(__n * sizeof(_Tp)))
                        : 0;
    }
    
    • deallocate: 释放 n 个对象的连续内存
    // __p is not permitted to be a null pointer.
      void deallocate(pointer __p, size_type __n)
        { _Alloc::deallocate(__p, __n * sizeof(_Tp)); }
    
    • construct: 在分配好的内存上构造对象
      void construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); }
    
    • destroy: 在分配好的内存上析构对象
      void destroy(pointer __p) { __p->~_Tp(); }
    

    3 alloc

    alloc allocator申请和释放内存通过alloc中的静态方法实现。

    class allocator {
      typedef alloc _Alloc;          // The underlying allocator.
    }
    
    

    alloc定义如下,其实是__default_alloc_template 的一个特化类

    typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;
    

    __default_alloc_template由一级内存池和二级内存池组成

    STL 内存池结构

    3.1 二级内存池

    二级内存池为一个静态数组,数组元素类型为_Obj*,每个数组元素即一个单向链表的头。 _S_free_list存储不同大小空闲内存块的链表头,如size为 8 的chunk_list的链表头为_S_free_list的第一个元素,size 为 16 的chunk_list对应第二个元素,以此类推

    private:
    # if defined(__SUNPRO_CC) || defined(__GNUC__) || defined(__HP_aCC)
        static _Obj* __STL_VOLATILE _S_free_list[];
            // Specifying a size results in duplicate def for 4.1
    # else
        static _Obj* __STL_VOLATILE _S_free_list[_NFREELISTS];
    

    _Obj类型:

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

    3.2 一级内存池

    一级内存池是一段连续的大缓冲区。其中_S_start_free表示可用内存开头,_S_end_free表示可用内存末尾, _S_heap_size统计所有堆上分配内存的大小总和。

      // Chunk allocation state.
      static char* _S_start_free;
      static char* _S_end_free;
      static size_t _S_heap_size;
    

    3.3 内存分配策略

    3.3.1 二级内存池中的分配策略

    对于 size 不超过最大_MAX_BYTES(128)的内存分配请求,尽量从二级内存池中分配:

    • 申请内存:首先根据size大小找到二级内存池中对应的 slot, 并获取空闲内存块链表的头,取出第一个内存块,并将其从链表中删除
    • 释放内存:根据size大小找到二级内存池中对应的 slot, 将需要释放的内存块插入到空闲内存块组成的链表的头部,并更新对应 slot 中的指针。

    3.3.2 整体流程

    因此,使用__default_alloc_template申请内存的总体流程如下:

    1. 判断申请内存字节数size是否超过最大_MAX_BYTES(128)
    2. 如果超过,调用malloc_alloc::allocate从堆上申请内存;
    3. 如果未超过,根据size大小索引到相应的空闲内存块链表,判断是否为空
    4. 如果非空,则走二级内存池中的分配策略
    5. 如果为空,申请20*size大小的内存,判断可用一级内存池的大小(即left_bytes)
    6. 如果left_bytes >= 20*size, 直接从从一级内存池分配
    7. 如果left_bytes >= size, 从一级内存池分配尽量多的size, 一部分用于内存分配,一部分用于放入二级内存池
    8. 如果left_bytes < size, 首先将一级内存池中剩余内存块插入到二级内存池中,然后通过malloc申请2 * __total_bytes + _S_round_up(_S_heap_size >> 4)大小的内存,作为一级内存池。最后再跳转到 6,返回可用内存地址,返回

    stl 申请内存流程

    3.3.3 __default_alloc_template 的线程安全性

    __default_alloc_template的执行 allocate 和 deallocate 时,都会针对一级内存池和二级内存池进行动态调整,因此 STL 中通过互斥锁保护这些临界资源

        // It would be nice to use _STL_auto_lock here.  But we
        // don't need the NULL check.  And we do need a test whether
        // threads have actually been started.
        class _Lock;
        friend class _Lock;
        class _Lock {
            public:
                _Lock() { __NODE_ALLOCATOR_LOCK; }
                ~_Lock() { __NODE_ALLOCATOR_UNLOCK; }
        };
    

    __NODE_ALLOCATOR_LOCK__NODE_ALLOCATOR_UNLOCK是这样定义的

    #   define __NODE_ALLOCATOR_LOCK if (threads && __us_rsthread_malloc) \
                    { _S_node_allocator_lock._M_acquire_lock(); }
    #   define __NODE_ALLOCATOR_UNLOCK if (threads && __us_rsthread_malloc) \
                    { _S_node_allocator_lock._M_release_lock(); }
    

    互斥锁又是怎么实现的呢?根据不同的平台有多种实现方式。其中之一便是使用 linux 下的 pthread lib

      pthread_mutex_t _M_lock;
      void _M_initialize()   { pthread_mutex_init(&_M_lock, NULL); }
      void _M_acquire_lock() { pthread_mutex_lock(&_M_lock); }
      void _M_release_lock() { pthread_mutex_unlock(&_M_lock); }
    

    4 杂项

    simple_alloc,debug_alloc 这两者同alloctor相似,不同点在于前三者将实际的内存分配器作为一个模板参数传入类中,然后调用其进行内存分配和释放。而后者内部直接使用alloc, 即__default_alloc_template<true, 0>

    4.1 simple_alloc

    主要用于 STL 哈希表和红黑树中节点的分配 模板参数中,_Tp表示元素类型,_Alloc表示实际的内存分配器

    template<class _Tp, class _Alloc>
    class simple_alloc {
    
    public:
        static _Tp* allocate(size_t __n)
          { return 0 == __n ? 0 : (_Tp*) _Alloc::allocate(__n * sizeof (_Tp)); }
        static _Tp* allocate(void)
          { return (_Tp*) _Alloc::allocate(sizeof (_Tp)); }
        static void deallocate(_Tp* __p, size_t __n)
          { if (0 != __n) _Alloc::deallocate(__p, __n * sizeof (_Tp)); }
        static void deallocate(_Tp* __p)
          { _Alloc::deallocate(__p, sizeof (_Tp)); }
    };
    

    4.2 debug_alloc

    debug_alloc: 元素类型默认为 char, 内存分配器通过模板参数指定 debug_alloc 实现中有一个比较有意思的地方:

    • 在申请内存时,多分配 8 个字节,用于记录分配的内存缓冲区的长度,给用户返回的缓冲区不包括这 64 位。
    • 在释放内存时,首先检查用户输入的内存缓冲区长度是否正确,然后将用户内存缓冲区和保存长度的 8 个字节一并释放。内存布局如下所示
    buf_len(8 Byte) | buf(n Byte)
    
    // Allocator adaptor to check size arguments for debugging.
    // Reports errors using assert.  Checking can be disabled with
    // NDEBUG, but it's far better to just use the underlying allocator
    // instead when no checking is desired.
    // There is some evidence that this can confuse Purify.
    template <class _Alloc>
    class debug_alloc {
    
    private:
    
      enum {_S_extra = 8};  // Size of space used to store size.  Note
                            // that this must be large enough to preserve
                            // alignment.
    
    public:
    
      static void* allocate(size_t __n)
      {
        char* __result = (char*)_Alloc::allocate(__n + (int) _S_extra);
        *(size_t*)__result = __n;
        return __result + (int) _S_extra;
      }
    
      static void deallocate(void* __p, size_t __n)
      {
        char* __real_p = (char*)__p - (int) _S_extra;
        assert(*(size_t*)__real_p == __n);
        _Alloc::deallocate(__real_p, __n + (int) _S_extra);
      }
    
      static void* reallocate(void* __p, size_t __old_sz, size_t __new_sz)
      {
        char* __real_p = (char*)__p - (int) _S_extra;
        assert(*(size_t*)__real_p == __old_sz);
        char* __result = (char*)
          _Alloc::reallocate(__real_p, __old_sz + (int) _S_extra,
                                       __new_sz + (int) _S_extra);
        *(size_t*)__result = __new_sz;
        return __result + (int) _S_extra;
      }
    
    };
    
    

    推荐阅读

    更多精彩内容,请扫码关注微信公众号:后端技术小屋。如果觉得文章对你有帮助的话,请多多分享、转发、在看。
    二维码

    4 条回复    2021-02-26 09:54:02 +08:00
    hxndg
        1
    hxndg  
       2021-02-24 21:16:39 +08:00
    我觉得挺好,lz 有没有横向对比的总结文章呢?
    此外,我为啥记得在多线程环境下,对于 vector 中的 iterator 进行 erase 会导致问题出现呢?
    这个还能说是线程安全的吗?
    nightwitch
        2
    nightwitch  
       2021-02-24 21:28:54 +08:00
    2021 年了,就别啃 2001 年的 SGI STL 了,完全脱离标准和主流实现了。论可读性 llvm 的 libcxx 并不比它差。

    SGI 的 allocator 实现包括一个内存池在 2001 年还可以参考下,从 2021 年的角度来看也不见得是个聪明的做法,因为现在 glibc 的 malloc 自身本身就包括一个很复杂的分配策略,并不是每次都要走 sbrk 系统调用。
    a554340466
        3
    a554340466  
       2021-02-24 23:24:43 +08:00 via iPhone
    ptmalloc 本身就有内存池了。不需要这玩意了。而且这个不还给 os
    hu8245
        4
    hu8245  
       2021-02-26 09:54:02 +08:00
    @nightwitch 说的很到位。昨天特意看了 libcxx 的 allocator 实现,确实 allocator 只是简单的对 malloc 和 free 的封装。侯捷在这个[视频](
    )中也说到了, 他还表达疑问:为什么这么优秀的策略(内存池)不用了呢。其实可能这些策略已经不需要了,内核的策略比这个优秀
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2889 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 14:20 · PVG 22:20 · LAX 07:20 · JFK 10:20
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.