史上最骚のSTL空间分配器 Surager

史上最骚のSTL内存池(一)

中规中矩的分配器

此分析是针对C++11以前的较低版本STL来说

allocator是一个对::operator new::operator delete的简单包装。没有较高的分配效率,因此常常被弃用。

以下是它的核心代码:

template <class T>
inline T* allocate(ptrdiff_t size,T*){
  set_new_handler(0);
  T* tmp = (T*)(::operator new((size_t)(size * sizeof(T)));
  if (tmp == 0){
    cerr << "Out of memory" << endl;
    exit(1);
  }
  return 0;
}
                
template <class T>
void deallocate(T* buffer){
  ::operator delete(buffer);
}

由此可见其简陋性。

特(zui)殊(sao)的分配器

基本思想

  1. 将内存空间的分配与释放和对象内容的构造与析构分开。

<stl_construct.h>中定义constructdistory函数,在<stl_alloc.h>中定义一个内存池。

  1. 采用多级配置器的内存处理方法。

第一级分配器直接使用mallocfree,第二层配置器视情况采用不同的分配策略。当内存块大于128bytes时视之为“足够大”,使用第一级配置器;当内存块小于128bytes时,视之为“过小”,则采用memory pool进行分配。

第一级配置器剖析

第一级配置器:__malloc_alloc_template

源码:

#if 0
#   include <new>
#   define __THROW_BAD_ALLOC throw bad_alloc
#elif !defined(__THROW_BAD_ALLOC)
#   include <iostream>
#define __THROW_BAD_ALLOC                      \
    std::cerr << "out of memory" << std::endl; \
    exit(1);
#endif

template <int inst>
class __malloc_alloc_template{
private:
    static void *oom_malloc(size_t);
    static void *oom_realloc(void *, size_t);
    static void (*__malloc_alloc_oom_handler)();

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

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

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

    static void (* set_malloc_handler(void (*f)()))(){
        void (*old)() = __malloc_alloc_oom_handler;
        __malloc_alloc_oom_handler = f;
        return (old);
    }
}; // end of __malloc_alloc_template

template <int inst>
void (*__malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = 0;

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(my_malloc_handler == 0) {
      __THROW_BAD_ALLOC;
    }
    (*my_malloc_handler)();
    result = malloc(n);
    if(result)
      return (result);
  }
}

template <int inst>
void * __malloc_alloc_template<inst>::oom_realloc(void *p,size_t n){
  void (*my_malloc_handler)();
  void *result;

  for (;;){
    my_malloc_handler = __malloc_alloc_oom_handler;
    if (my_malloc_handler == 0){
      __THROW_BAD_ALLOC;
    }
    (*my_malloc_handler)();
    result = malloc(n);
    if(result)
      return (result);
  }
}

程序使用了mallocfreerealloc 进行内存的分配、释放和重分配。因为c++没有提供对应realloc()的操作,因此不能直接使用set_new_handler()。因此仿真了一个类似的set_new_handler()

另外程序在内存不足时使用递归调用的“内存不足处理”函数。期望每次调用获得足够的内存而圆满完成任务。

第二级配置器剖析

第二级配置器:__default_alloc_template

这一级配置器以内存池管理。每一次配置一大块内存,并维护对应的自由链表。下次再有相同大小的内存需求,就直接从free-lists中拔出。用户归还内存时,配置器会将其回收到free-lists中。此外,为了方便管理,二级配置器会自动把小块内存上调至8的倍数。自由链表有16个,他们管理的大小分别为8,16,24,32,40,48,56,64,72,80,88,96,104,112,120,128bytes。

部分源码:

enum {__ALIGN = 8};
enum {__MAX_BYTES = 128};
enum {__NFREELISTS = __MAX_BYTES/__ALIGN};

template <bool threads,int inst>
class __default_alloc_template{
private:
    static size_t ROUND_UP(size_t bytes){
        return (((bytes) + __ALIGN - 1) & ~(__ALIGN - 1));
    }
private:
    union obj
    {
        union obj *free_list_link;
        char client_date[1];
    };
private:
    static obj *volatile free_list[__NFREELISTS];
    static size_t FREELIST_INDEX(size_t bytes){
        return (((bytes) + __ALIGN - 1) / __ALIGN - 1);
    }
    static void *refill(size_t n);
    static char *chunk_alloc(size_t size, int &nobjs);

    static char *start_free;
    static char *end_free;
    static size_t heap_size;

public:
    static void *allocate(size_t n);
    static void deallocate(void *p,size_t n);
    static void *reallocate(void *p, size_t old_sz, size_t new_sz);
}; // end of __default_alloc_template

template <bool threads, int inst>
char *__default_alloc_template<threads, inst>::start_free = 0;

template <bool threads, int inst>
char *__default_alloc_template<threads, inst>::end_free = 0;

template <bool threads, int inst>
size_t __default_alloc_template<threads, inst>::heap_size = 0;

template <bool threads, int inst>
__default_alloc_template<threads, inst>::obj *volatile __default_alloc_template<threads, inst>::free_list[__NFREELISTS] =
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,};

每个节点用一个联合体obj组成。它相当于一个指针。这样做其实是为了不浪费额外的内存。

在二级配置器中,allocate首先判断区块的大小,如果小于128bytes就调用第一级配置器,小于128bytes时就去检查对应的free_list。如果没有可用的内存块,就上调大小,并调用refill。

static void *allocate(size_t n){
    obj *volatile * my_free_list;
    obj *result;

    if (n > (size_t) __MAX_BYTES){
      return (malloc_alloc::allocate(n));
    }

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

很清晰。

deallocate也是同样的思路。

static void deallocate(void *p,size_t n){
    obj *q = (obj *)p;
    obj *volatile *my_free_list;

    if (n > (size_t) __MAX_BYTES){
      q = malloc_alloc::deallocate(p, n);
      return;
    }

    my_free_list = free_list + FREELIST_INDEX(n);
    q->free_list_link = *my_free_list;
    *my_free_list = q;
}

对于reallocate,直接使用上面的两个现成函数即可。

static void *reallocate(void *p, size_t old_sz, size_t new_sz){
    deallocate(p, old_sz);
    p = allocate(new_sz);
    return p;
}

重新装填refill

在allocate发现free list中没有合适的区块时,调用refill进行重新装填。缺省得到20个新节点,但是有时内存不足,可能得不到这么多。

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 (nobjs == 1) // Only one free list returned
        return (chunk);
    // ready to adjust the free list
    my_free_list = free_list + FREELIST_INDEX(n);

    result = (obj *)chunk; // this chunk will be returned
    *my_free_list = next_obj = (obj *)(chunk + n);

    for (i = 1;;i++){ // add all the chunks to free list
        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);
}

返回20个新节点并将其加入到free list中,成为链表的一部分。