浅谈C++空间配置器allocator

目录
  • 概述
  • 1. Allocator 的标准接口
  • 2. SGI STL 内存分配失败的异常处理
  • 3. SGI STL 内置轻量级内存池的实现
  • 4. SGI STL 内存池在多线程下的互斥访问

概述

在C++中,一个对象的内存配置和释放一般都包含两个步骤,对于内存的配置,首先是调用operator new来配置内存,然后调用对象的类的构造函数进行初始化;而对于内存释放,首先是调用析构函数,然后调用 operator delete进行释放。 如以下代码:

class Foo { ... };
Foo* pf = new Foo;
...
delete pf;

Allocator 的作用相当于operator new 和operator delete的功能,只是它考虑得更加细致周全。SGI STL 中考虑到了内存分配失败的异常处理,内置轻量级内存池(主要用于处理小块内存的分配,应对内存碎片问题)实现, 多线程中的内存分配处理(主要是针对内存池的互斥访问)等,本文就主要分析 SGI STL 中在这三个方面是如何处理的。在介绍着三个方面之前,我们先来看看 Allocator的标准接口。

1. Allocator 的标准接口

在 SGI STL 中,Allocator的实现主要在文件alloc.h和stl_alloc.h文件中。根据 STL 规范,Allocator 需提供如下的一些接口(见stl_alloc.h文件的第588行开始的class template allocator):

// 标识数据类型的成员变量,关于中间的6个变量的涵义见后续文章(关于Traits编程技巧)
typedef alloc _Alloc;
typedef size_t     size_type;
typedef ptrdiff_t  difference_type;
typedef _Tp*       pointer;
typedef const _Tp* const_pointer;
typedef _Tp&       reference;
typedef const _Tp& const_reference;
typedef _Tp        value_type;
template <class _Tp1> struct rebind {
  typedef allocator<_Tp1> other;
}; // 一个嵌套的class template,仅包含一个成员变量 other
// 成员函数
allocator() __STL_NOTHROW {}  // 默认构造函数,其中__STL_NOTHROW 在 stl_config.h中定义,要么为空,要么为 throw()
allocator(const allocator&) __STL_NOTHROW {}  // 拷贝构造函数
template <class _Tp1> allocator(const allocator<_Tp1>&) __STL_NOTHROW {} // 泛化的拷贝构造函数
~allocator() __STL_NOTHROW {} // 析构函数
pointer address(reference __x) const { return &__x; } // 返回对象的地址
const_pointer address(const_reference __x) const { return &__x; }  // 返回const对象的地址
_Tp* allocate(size_type __n, const void* = 0) {
  return __n != 0 ? static_cast<_Tp*>(_Alloc::allocate(__n * sizeof(_Tp))) : 0;
  // 配置空间,如果申请的空间块数不为0,那么调用 _Alloc 也即 alloc 的 allocate 函数来分配内存,
} //这里的 alloc 在 SGI STL 中默认使用的是__default_alloc_template<__NODE_ALLOCATOR_THREADS, 0>这个实现(见第402行)
void deallocate(pointer __p, size_type __n) { _Alloc::deallocate(__p, __n * sizeof(_Tp)); } // 释放空间
size_type max_size() const __STL_NOTHROW  // max_size() 函数,返回可成功配置的最大值
    { return size_t(-1) / sizeof(_Tp); }  //这里没看懂,这里的size_t(-1)是什么意思?
void construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); } // 调用 new 来给新变量分配空间并赋值
void destroy(pointer __p) { __p->~_Tp(); } // 调用 _Tp 的析构函数来释放空间

在SGI STL中设计了如下几个空间分配的 class template:

template <int __inst> class __malloc_alloc_template // Malloc-based allocator.  Typically slower than default alloc
typedef __malloc_alloc_template<0> malloc_alloc
template<class _Tp, class _Alloc> class simple_alloc
template <class _Alloc> class debug_alloc
template <bool threads, int inst> class __default_alloc_template // Default node allocator.
typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc
typedef __default_alloc_template<false, 0> single_client_alloc
template <class _Tp>class allocator
template<>class allocator<void>
template <class _Tp, class _Alloc>struct __allocator
template <class _Alloc>class __allocator<void, _Alloc>

其中simple_alloc,debug_alloc,allocator和__allocator的实现都比较简单,都是对其他适配器的一个简单封装(因为实际上还是调用其他配置器的方法,如_Alloc::allocate)。而真正内容比较充实的是__malloc_alloc_template和__default_alloc_template这两个配置器,这两个配置器就是 SGI STL 配置器的精华所在。其中__malloc_alloc_template是SGI STL 的第一层配置器,只是对系统的malloc,realloc函数的一个简单封装,并考虑到了分配失败后的异常处理。而__default_alloc_template是SGI STL 的第二层配置器,在第一层配置器的基础上还考虑了内存碎片的问题,通过内置一个轻量级的内存池。下文将先介绍第一级配置器的异常处理机制,然后介绍第二级配置器的内存池实现,及在多线程环境下内存池互斥访问的机制。

2. SGI STL 内存分配失败的异常处理

内存分配失败一般是由于out-of-memory(oom),SGI STL 本身并不会去处理oom问题,而只是提供一个 private 的函数指针成员和一个 public 的设置该函数指针的方法,让用户来自定义异常处理逻辑:

private:
#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
  static void (* __malloc_alloc_oom_handler)();  // 函数指针
#endif
public:
  static void (* __set_malloc_handler(void (*__f)()))() // 设置函数指针的public方法
  {
    void (* __old)() = __malloc_alloc_oom_handler;
    __malloc_alloc_oom_handler = __f;
    return(__old);
  }

如果用户没有调用该方法来设置异常处理函数,那么就不做任何异常处理,仅仅是想标准错误流输出一句out of memory并退出程序(对于使用new和C++特性的情况而言,则是抛出一个std::bad_alloc()异常), 因为该函数指针的缺省值为0,此时对应的异常处理是__THROW_BAD_ALLOC:

// line 152 ~ 155
#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
template <int __inst>
void (* __malloc_alloc_template<__inst>::__malloc_alloc_oom_handler)() = 0;
#endif
// in _S_oom_malloc and _S_oom_realloc
__my_malloc_handler = __malloc_alloc_oom_handler;
if (0 == __my_malloc_handler) { __THROW_BAD_ALLOC; }
// in preprocess, line 41 ~ 50
#ifndef __THROW_BAD_ALLOC
#  if defined(__STL_NO_BAD_ALLOC) || !defined(__STL_USE_EXCEPTIONS)
#    include <stdio.h>
#    include <stdlib.h>
#    define __THROW_BAD_ALLOC fprintf(stderr, "out of memory\n"); exit(1)
#  else /* Standard conforming out-of-memory handling */
#    include <new>
#    define __THROW_BAD_ALLOC throw std::bad_alloc()
#  endif
#endif

SGI STL 内存配置失败的异常处理机制就是这样子了,提供一个默认的处理方法,也留有一个用户自定义处理异常的接口。

3. SGI STL 内置轻量级内存池的实现

第一级配置器__malloc_alloc_template仅仅只是对malloc的一层封装,没有考虑可能出现的内存碎片化问题。内存碎片化问题在大量申请小块内存是可能非常严重,最终导致碎片化的空闲内存无法充分利用。SGI 于是在第二级配置器__default_alloc_template中 内置了一个轻量级的内存池。 对于小内存块的申请,从内置的内存池中分配。然后维护一些空闲内存块的链表(简记为空闲链表,free list),小块内存使用完后都回收到空闲链表中,这样如果新来一个小内存块申请,如果对应的空闲链表不为空,就可以从空闲链表中分配空间给用户。具体而言SGI默认最大的小块内存大小为128bytes,并设置了128/8=16 个free list,每个list 分别维护大小为 8, 16, 24, …, 128bytes 的空间内存块(均为8的整数倍),如果用户申请的空间大小不足8的倍数,则向上取整。

SGI STL内置内存池的实现请看__default_alloc_template中被定义为 private 的这些成员变量和方法(去掉了部分预处理代码和互斥处理的代码):

private:
#if ! (defined(__SUNPRO_CC) || defined(__GNUC__))
    enum {_ALIGN = 8}; // 对齐大小
    enum {_MAX_BYTES = 128}; // 最大有内置内存池来分配的内存大小
    enum {_NFREELISTS = 16}; // _MAX_BYTES/_ALIGN  // 空闲链表个数
# endif
  static size_t  _S_round_up(size_t __bytes) // 不是8的倍数,向上取整
    { return (((__bytes) + (size_t) _ALIGN-1) & ~((size_t) _ALIGN - 1)); }
__PRIVATE:
  union _Obj { // 空闲链表的每个node的定义
        union _Obj* _M_free_list_link;
        char _M_client_data[1];   };
  static _Obj* __STL_VOLATILE _S_free_list[]; // 空闲链表数组
  static size_t _S_freelist_index(size_t __bytes) { // __bytes 对应的free list的index
        return (((__bytes) + (size_t)_ALIGN-1)/(size_t)_ALIGN - 1);
  }
  static void* _S_refill(size_t __n); // 从内存池中申请空间并构建free list,然后从free list中分配空间给用户
  static char* _S_chunk_alloc(size_t __size, int& __nobjs); // 从内存池中分配空间
  static char* _S_start_free;  // 内存池空闲部分的起始地址
  static char* _S_end_free; // 内存池结束地址
  static size_t _S_heap_size; // 内存池堆大小,主要用于配置内存池的大小

函数_S_refill的逻辑是,先调用_S_chunk_alloc从内存池中分配20块小内存(而不是用户申请的1块),将这20块中的第一块返回给用户,而将剩下的19块依次链接,构建一个free list。这样下次再申请同样大小的内存就不用再从内存池中取了。有了_S_refill,用户申请空间时,就不是直接从内存池中取了,而是从 free list 中取。因此allocate和reallocate在相应的free list为空时都只需直接调用_S_refill就行了。其中_S_refill和_S_chunk_alloc这两个函数是该内存池机制的核心。

__default_alloc_template对外提供的 public 的接口有allocate,deallocate和reallocate这三个,其中涉及内存分配的allocate和reallocate的逻辑思路是,首先看申请的size(已round up)对应的free list是否为空,如果为空,则调用_S_refill来分配,否则直接从对应的free list中分配。而deallocate的逻辑是直接将空间插入到相应free list的最前面。

这里默认是依次申请20块,但如果内存池空间不足以分配20块时,会尽量分配足够多的块,这些处理都在_S_chunk_alloc函数中。该函数的处理逻辑如下(源代码这里就不贴了):

1) 能够分配20块

从内存池分配20块出来,改变_S_start_free的值,返回分配出来的内存的起始地址

2) 不足以分配20块,但至少能分配一块

分配经量多的块数,改变_S_start_free的值,返回分配出来的内存的起始地址

3) 一块也分配不了

首先计算新内存池大小size_t __bytes_to_get = 2 * __total_bytes + _S_round_up(_S_heap_size >> 4)
将现在内存池中剩余空间插入到适当的free list中调用malloc来获取一大片空间作为新的内存池:

– 如果分配成功,则调整_S_end_free和_S_heap_size的值,并重新调用自身,从新的内存池中给用户分配空间; – 否则,分配失败,考虑从比当前申请的空间大的free list中分配空间,如果无法找不到这样的非空free list,则调用第一级配置器的allocate,看oom机制能否解决问题。

SGI STL的轻量级内存池的实现就是酱紫了,其实并不复杂。

4. SGI STL 内存池在多线程下的互斥访问

最后,我们来看看SGI STL中如何处理多线程下对内存池互斥访问的(实际上是对相应的free list进行互斥访问,这里访问是只需要对free list进行修改的访问操作)。在SGI的第二级配置器中与内存池互斥访问相关的就是_Lock这个类了,它仅仅只包含一个构造函数和一个析构函数,但这两个函数足够了。在构造函数中对内存池加锁,在析构函数中对内存池解锁:

//// in __default_alloc_template
# ifdef __STL_THREADS
    static _STL_mutex_lock _S_node_allocator_lock; // 互斥锁变量
# endif
class _Lock {
    public:
        _Lock() { __NODE_ALLOCATOR_LOCK; }
        ~_Lock() { __NODE_ALLOCATOR_UNLOCK; }
};
//// in preprocess
#ifdef __STL_THREADS
# include <stl_threads.h> // stl 的线程,只是对linux或windows线程的一个封装
# define __NODE_ALLOCATOR_THREADS true
# ifdef __STL_SGI_THREADS
#   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(); }  // 释放锁
# else /* !__STL_SGI_THREADS */
#   define __NODE_ALLOCATOR_LOCK \
        { if (threads) _S_node_allocator_lock._M_acquire_lock(); }
#   define __NODE_ALLOCATOR_UNLOCK \
        { if (threads) _S_node_allocator_lock._M_release_lock(); }
# endif
#else /* !__STL_THREADS */
#   define __NODE_ALLOCATOR_LOCK
#   define __NODE_ALLOCATOR_UNLOCK
#   define __NODE_ALLOCATOR_THREADS false
#endif

由于在__default_alloc_template的对外接口中,只有allocate和deallocate中直接涉及到对free list进行修改的操作,所以在这两个函数中,在对free list进行修改之前,都要实例化一个_Lock的对象__lock_instance,此时调用构造函数进行加锁,当函数结束时,的对象__lock_instance自动析构,释放锁。这样,在多线程下,可以保证free list的一致性。

以上就是浅谈C++空间配置器allocator的详细内容,更多关于C++空间配置器allocator的资料请关注我们其它相关文章!

(0)

相关推荐

  • C++中多态的定义及实现详解

    1. 多态概念 1.1 概念 多态的概念:通俗来说,就是多种形态,具体点就是去完成某个行为,当不同的对象去完成时会产生出不同的状态. 举个栗子:比如买票,当普通人买票时,是全价买票:学生买票时,是半价买票:军人买票时是优先买票.同一个事情针对不同的人或情况有不同的结果或形态. 2. 多态的定义及实现 2.1 多态的构成条件 多态是在不同继承关系的类对象,去调用同一函数,产生了不同的行为.比如Student继承了Person. Person对象买票全价,Student对象买票半价. 注意:那么在继

  • C++如何计算结构体与对象的大小

    如何计算结构体的大小 其实计算一个结构的大小的方法并不难,简单来说就是把结构体内的所有成员的大小相加就可以.但是,需要内存对齐那么究竟什么是内存对齐,又为什么要进行类型对齐呢? 结构体的内存对齐 结构体内存对齐主要有两个步骤: 1.结构体各成员对齐. 2.结构体总体对齐 结构体内存对齐规则: 1.结构体的第一个成员在存放在结构体偏移量为0的位置 2.其他成员变量要对齐到某个数字(对齐数)的整数倍的地址处.. 对齐数 = 编译器默认的一个对齐数与该成员大小的较小值. /* **VS中默认的值为8

  • 使用c++11 constexpr时遇到的坑详解

    最近在使用constexpr的时候无意中踩了个小坑. 下面给个小示例: #include <iostream> constexpr int n = 10; constexpr char *msg = "Hello, world!"; int main() { for (auto i = 0; i < n; ++i) { std::cout << msg << std::endl; } } constexpr应该是大家很熟悉的东西了,也是最常用的

  • C++ 虚函数表图文解析

    一.前言 一直以来,对虚函数的理解仅仅是,在父类中定义虚函数,子类中可以重写该虚函数,并且父类指针可以指向子类对象,调用子类的虚函数(多态).在读研阶段经历的几个项目中,自己所写的类中并没有用到虚函数,对虚函数这个东西的强大之处并没有太多体会.最近,学了设计模式中的简单工厂模式,对多态有了具体的认识.于是,补了补多态.虚函数.虚函数表相关的知识,参考相关博客,加上自己的理解,整理了这篇博文. 二.含有虚函数类的内存模型 以下面的类为例(32位平台下): class Father { public

  • C++ 组合 (Composition)的介绍与实例

    概述 c++中一个重要的特点就是代码的重用,为了代码重用,有两个非常重要的手段,一个是继承,一个是组合 组合 (Composition) 指在一个类中另一类的对象作为数据成员. 案例 在平面上两点连成一条直线, 求直线的长度和直线中点的坐标. 要求: 基类: Dot 派生类: Line (同时组合) 派生类 Line 从基类 Dot 继承的 Dot 数据, 存放直线的中点坐标 Line 类再增加两个 Dot 对象, 分别存放两个端点的坐标 Dot 类: #ifndef PROJECT5_DOT_

  • C++中对象&类的深入理解

    什么是对象 任何事物都是一个对象, 也就是传说中的万物皆为对象. 对象的组成: 数据: 描述对象的属性 函数: 描述对象的行为, 根据外界的信息进行相应操作的代码 具有相同的属性和行为的对象抽象为类 (class) 类是对象的抽象 对象则是类的特例 面向过程 vs 面向对象 面向过程 面向过程的设计: 围绕功能, 用一个函数实现一个功能 程序 = 算法 +数据结构 算法和数据结构两者互相独立, 分开设计 面向对象 面向对象的设计: 把算法和数据封装在一个对象中 设计所需要的歌者类和对象 向有关对

  • C++中的多态详谈

    1. 多态概念 1.1 概念 多态的概念:通俗来说,就是多种形态,具体点就是去完成某个行为,当不同的对象去完成时会产生出不同的状态. 举个栗子:比如买票,当普通人买票时,是全价买票:学生买票时,是半价买票:军人买票时是优先买票.同一个事情针对不同的人或情况有不同的结果或形态. 2. 多态的定义及实现 2.1 多态的构成条件 多态是在不同继承关系的类对象,去调用同一函数,产生了不同的行为.比如Student继承了Person. Person对象买票全价,Student对象买票半价. 注意:那么在继

  • C++中的常用库

    1. cmath: 数学计算 #include <iostream> #include <cmath> using namespace std; int main () { // 数字定义 short s = 10; int i = -1000; long l = 100000; float f = 230.47; double d = 200.374; // 数学运算 cout << "sin(d) :" << sin(d) <&

  • 关于C/C++内存管理示例详解

    1.内存分配方式 在C++中,内存分成五个区,分别是堆.栈.自由存储区.静态存储区和常量存储区. 1) 栈 执行函数时,函数内局部变量的存储单元都可以在栈上创建,函数执行结束时这些存储单元自动被释放.栈内存分配运算内置处理器指令集中,效率很高,但分配的内存容量有限. 2) 堆 由new分配的内存块,释放由程序员控制.如果程序员没有释放,那么就在程序结束的时候,被操作系统回收. 3) 自由存储区 由malloc等分配的内存块,用free结束自己的生命. 4) 静态存储区 全局变量和静态变量被分配到

  • 浅谈C++空间配置器allocator

    目录 概述 1. Allocator 的标准接口 2. SGI STL 内存分配失败的异常处理 3. SGI STL 内置轻量级内存池的实现 4. SGI STL 内存池在多线程下的互斥访问 概述 在C++中,一个对象的内存配置和释放一般都包含两个步骤,对于内存的配置,首先是调用operator new来配置内存,然后调用对象的类的构造函数进行初始化:而对于内存释放,首先是调用析构函数,然后调用 operator delete进行释放. 如以下代码: class Foo { ... }; Foo

  • 浅谈Tomcat内存配置的正确姿势

    1.背景 虽然阅读了各大牛的博客或文章,但并没有找到特别全面的关于JVM内存分配方法的文章,很多都是复制黏贴 为了严谨,本文特别备注只介绍基于HotSpot VM虚拟机,并且基于JDK1.7的内存分配情况,有关GC的说法也是基于CMS的concurrent collection(而非G1),防止大牛拍砖. 目前主流的JVM就是HotSpot VM(其次还有J9 VM,Zing VM),目前各类博客文章也大多基于JDK1.7以前的版本进行阐述的. (注:因为不同的虚拟机实现,不同的JDK,内存的分

  • 浅谈Springboot实现拦截器的两种方式

    目录 一.拦截器方式 1.配置HandlerInterceptor 2.注册拦截器 3.使用拦截器的坑 二.过滤器方式 1.实现Filter接口 2.使用过滤器需要注意的 实现过滤请求有两种方式: 一种就是用拦截器,一种就是过滤器 拦截器相对来说比较专业,而过滤器虽然不专业但是也能完成基本的拦截请求要求. 一.拦截器方式 1.配置HandlerInterceptor 下面这个也是我们公司项目拦截器的写法,总体来说感觉还不错,我就记录了下来. 利用了一个静态Pattern变量存储不走拦截器的路径,

  • 浅谈三种配置linux环境变量的方法(以java为例)

    1. 修改/etc/profile文件 如果你的计算机仅仅作为开发使用时推荐使用这种方法,因为所有用户的shell都有权使用这些环境变量,可能会给系统带来安全性问题. ·用文本编辑器打开/etc/profile ·在profile文件末尾加入: export JAVA_HOME=/usr/share/jdk1.6.0_14 export PATH=$JAVA_HOME/bin:$PATH export CLASSPATH=.:$JAVA_HOME/lib/dt.jar:$JAVA_HOME/li

  • 浅谈webpack-dev-server的配置和使用

    本文介绍了浅谈webpack-dev-server的配置和使用,分享给大家,具体如下: 1安装的WebPack-dev-server 在终端输入 npm i webpack-dev-server 安装webpack-dev-server包 2.配置dev-server 在package.json文件中的脚本中添加代码 "dev":"WebPack-dev-server --config webpack.config.js" 在webpack.config.js文件中

  • 浅谈SpringMVC的拦截器(Interceptor)和Servlet 的过滤器(Filter)的区别与联系 及SpringMVC 的配置文件

    1.过滤器: 依赖于servlet容器.在实现上基于函数回调,可以对几乎所有请求进行过滤,但是缺点是一个过滤器实例只能在容器初始化时调用一次.使用过滤器的目的是用来做一些过滤操作,获取我们想要获取的数据. 比如:在过滤器中修改字符编码:在过滤器中修改 HttpServletRequest的一些参数,包括:过滤低俗文字.危险字符等 关于过滤器的一些用法可以参考我写过的这些文章: 继承HttpServletRequestWrapper以实现在Filter中修改HttpServletRequest的参

  • 浅谈IIS安全配置

    1.VPS或者服务器分区要是NTFS的原因不说了,说多了也没用 2.禁止TCP/IP的NETBIOS 通过网络属性的绑定选项,废止NetBIOS与TCP/IP之间的绑定 3.网站右键权限user(最好一个网站建立一个用户,尽可能不要相同)中权限 写入 执行等权限慎用,写入之后有可能会sql注入 坑爹的~~我就挨过一次 4.iis权限配置(重点剖析) 在站点-属性-主目录有这几个权限设置 脚本资源访问 写入 浏览 记录访问 索引资源 这些我一般推荐就打开浏览和脚本访问 有的系统需求的话,就对应目录

  • 从入侵者的角度浅谈服务器安全配置基本知识

    目前较为流行web入侵方式都是通过寻找程序的漏洞先得到网站的webshell然后再根据服务器的配置来找到相应的可以利用的方法进行提权,进而拿下服务器权限的.所以配合服务器来设置防止webshell是有效的方法. 一.防止数据库被非法下载 应当说,有一点网络安全的管理员,都会把从网上下载的网站程序的默认数据库路径进行更改.当然也有一部分管理员非常粗心,拿到程序直接在自己的服务器上进行安装,甚至连说明文件都不进行删除,更不要说更改数据库路径了.这样黑客就可以通过直接从源码站点下载网站源程序,然后在本

  • 浅谈Gradle 常用配置总结

    这里分享下我在日常开发中对 Gradle 的常用配置规则 一.版本号配置 当项目逐渐演进的过程中,主工程依赖的 Module 可能会越来越多,此时就需要统一配置各个 Module 的编译参数了 在工程的根目录下新建一个 gradle 文件,命名为 config.gradle ,在此文件中统一声明工程的编译属性和依赖库的版本号 ext { compileSdkVersion = 28 minSdkVersion = 15 targetSdkVersion = 28 versionCode = 1

  • 浅谈springboot自动配置原理

    从main函数说起 一切的开始要从SpringbootApplication注解说起. @SpringBootApplication public class MyBootApplication { public static void main(String[] args) { SpringApplication.run(MyBootApplication.class); } } @SpringBootConfiguration @EnableAutoConfiguration @Compon

随机推荐